背包问题全解

搞懂背包的关键
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];
    }