今天给一个烙印解释一个背包的变种，dp问题，差点吐血 - JobHunting版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - 今天给一个烙印解释一个背包的变种，dp问题，差点吐血

相关主题
● [算法] unsorted array
● 讨论做题：find kth smallest number in two sorted arrays at
● 关于 unique paths，总是过不了 OJ，请牛牛们帮忙看看~~~先谢过。。。
● 求问三道板上面经总结来的题，希望牛们给点思路
● 问个sorting的题目
● [合集] 请教个经典面试题的变种
● 昨天有人讲过的啥de啥的是怎么回事有人知道么
● 终于弄明白median of two sorted arrays了，发帖庆祝一下
● Ebay 三轮skype面筋（免onsite Offer）
● 请教一道题

相关话题的讨论汇总
话题: index话题: arr话题: dp话题: int话题: target

进入JobHunting版参与讨论

(共1页)

u***8
发帖数: 1581

面试的。真不知道这是如何进的公司。还面试我。
给你一个number，一组数，比如30，50，100（可能更多个数，sorted的），求组合这
些数得到最小的大于target的数。
public int getMin(int[] arr, int target) {
boolean[] dp = new boolean[target + arr[arr.length-1]];
dp[0] = true;
for (int index = arr[0]; index < dp.length; index++ ) {
for (int i = 0; i < arr.length; i++) {
if (index-arr[i] >= 0 && dp[index- arr[i]]) {
dp[index] = true;
if (index>= target)
return index;
break;
}
}
}
return -1;
}
讲了30分钟。。。
当然，我把 if (index>= target)
return index;
一急之下，写到了第2个for的外面，也是错了。但是，ta都没看出来。sigh。

(共1页)

进入JobHunting版参与讨论

相关主题
● 请教一个问题的答案，好像以前有人讨论过
● 请教一个常见的面试题的答案
● Another amazon interview questions
● 问个面试题
● 算法面试题
● 新鲜Amazon面经(附参考答案) 顺便求各种大公司refer
● 问一道老题
● 这题咋做？
● 求教一个题目,sudoku 下面代码哪里错了。。。
● Leetcode Timeout

相关话题的讨论汇总
话题: index话题: arr话题: dp话题: int话题: target

boards