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

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

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

相关主题
● [算法] unsorted array	● Ebay 三轮skype面筋（免onsite Offer）
● 讨论做题：find kth smallest number in two sorted arrays at	● 请教一道题
● 关于 unique paths，总是过不了 OJ，请牛牛们帮忙看看~~~先谢过。。。	● 请教一个问题的答案，好像以前有人讨论过
● 求问三道板上面经总结来的题，希望牛们给点思路	● 请教一个常见的面试题的答案
● 问个sorting的题目	● Another amazon interview questions
● [合集] 请教个经典面试题的变种	● 问个面试题
● 昨天有人讲过的啥de啥的是怎么回事有人知道么	● 算法面试题
● 终于弄明白median of two sorted arrays了，发帖庆祝一下	● 新鲜Amazon面经(附参考答案) 顺便求各种大公司refer

相关话题的讨论汇总
话题: 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版参与讨论

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

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

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天