动态规划-和为k的组合数

第一行:手中金钱为money,商品数量为n

第二行:商品的价格表例如[3, 7, 5, 10, 5]

问:选择某些商品,使得价格正好为money(商品不可重复选择,价格相同的算不同商品);如果没有,则返回-1


刚开始用了回溯法,傻逼了;后来想到了动态规划

public int solve(int[] prices, int target) {
        /**
         * dp[i][j]:可选商品为前i个时,凑出总价为j的组合数
         * 求dp[n][target]
         */
        int n = prices.length;
        int[][] dp = new int[n+1][target+1];

        // 初始化,和为0的组合数为0
        for (int i = 0; i <= n; i++) dp[i][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                if (prices[i-1] <= j) {   // 第i个商品的价格小于等于当前总价,可以买/也可以不买
                    dp[i][j] = dp[i-1][j-prices[i-1]] + dp[i-1][j];
                } else {  // 第i个商品的价格大于当前总价,不能买
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n][target];
    }

 

动态规划-和为k的组合数

上一篇:异步状态机


下一篇:CSS line-height 和 vertical-align 精解(下篇)