搞懂背包的关键
https://blog.csdn.net/XuNeely/article/details/112025393
空间优化的关键
https://blog.csdn.net/qq_xuanshuang/article/details/104031793
LintCode
problem 801 背包问题X
描述
你总共有n元，商人总共有三种商品，它们的价格分别是150元,250元,350元，三种商品的数量可以认为是无限多的，购买完商品以后需要将剩下的钱给商人作为小费，求最少需要给商人多少小费
样例 1:
输入: n = 900
输出: 0
样例 2:
输入: n = 800
输出: 0
进行了空间优化，运行length次，每运行一次，代表前i个能够组成的不大于j的最大值。
public int Solution(int n) {
int[] prices = new int[]{150, 250, 350};
int length = prices.length;
int[] dp = new int[n + 1];
for(int i = 0; i < length; i++) {
for(int j = 0; j <= n; j++) {
if(i == 0) {
//i == 0 说明是第一次运行，进行初始化
if(j >= prices[i]) {
dp[j] = (j / prices[i]) * prices[i];
} else {
dp[j] = 0;
}
} else {
if(j >= prices[i]) {
//这里一直出错！！！细心一点
//错误示例：dp[j] = Math.max(dp[j], dp[j - prices[i]]);
dp[j] = Math.max(dp[j], prices[i] + dp[j - prices[i]]);
}
}
}
}
return n - dp[n];
}
