讨论/《中级算法》 - 零钱兑换/
《中级算法》 - 零钱兑换
共 5 个回复

尝试设dp[i][j]为前i 种硬币组成金额j 时所使用的最小硬币数,枚举所有子问题时发现非常复杂,感觉不对劲,动态规划题的状态转移方程一般都是简单优美的,遂放弃。

然后尝试设dp[i]为金额i + 1时所使用的最小硬币数,枚举所有子问题时发现比上述假设更加简明,针对输入nums = [1,2,5] & amount = 11求解,大致过程如下:

1 dp[0] = 1 / nums[0] = 1
2 dp[1] = 2 / nums[1] = 1
3 dp[2] = dp[1] + dp[0] = 1 + 1 = 2
4 dp[3] = dp[1] + dp[1] = 1 + 1 = 2
5 dp[4] = 5 / nums[2] = 1
6 dp[5] = dp[4] + dp[0] = 1 + 1 = 2
7 dp[6] = Math.min(dp[5] + dp[0], dp[4] + dp[1], dp[3] + dp[2]) = Math.max(3, 2, 4) = 2
8 dp[7] = Math.min(dp[6] + dp[0], dp[5] + dp[1], dp[4] + dp[2], dp[3] + dp[3]) = Math.min(3, 3, 3, 4) = 3
9 dp[8] = Math.min(dp[7] + dp[0], dp[6] + dp[1], dp[5] + dp[2], dp[4] + dp[3]) = Math.min(4, 3, 4, 3) = 3
10 dp[9] = Math.min(dp[8] + dp[0], dp[7] + dp[1], dp[6] + dp[2], dp[5] + dp[3], dp[4] + dp[4]) = Math.min(4, 4, 4, 4, 2) = 2
11 dp[10] = Math.min(dp[9] + dp[0], dp[8] + dp[1], dp[7] + dp[2], dp[6] + dp[3], dp[5] + dp[4]) = Math.min(3, 4, 5, 4, 3) = 3

发现了当前项与之前几项的关系:

dp[i] = Math.min(dp[i - 1] + dp[0], dp[i - 2], + dp[1], ... , dp[i - Math.ceil(i / 2)] + dp[Math.ceil(i / 2)]);

另有特殊情况,就是当前金额i + 1 可以被尽可能大的硬币面额整除时,此时的商一定是最优解(最小硬币数量)。虽然问题解决了,但解法有点绕弯了,该解法覆盖了所有可能的面额组合,没有发现解空间内所有子问题解之间更本质的关系,因而没有剔除不必要的计算,勉强通过所有Case,TS 实现如下:

function coinChange(coins: number[], amount: number): number {
    const dp = [0];
    for (let i = 0; i < amount; i++) {
        let min = Infinity;
        for (let c of coins) {
            if ((i + 1) % c === 0) {
                min = Math.min(min, (i + 1) / c);
            }
        }
        for (let j = 0; j < Math.ceil(i / 2); j++) {
            min = Math.min(min, dp[j] + dp[i - 1 - j]);
        }
        dp[i] = min;
    }
    return dp[dp.length - 1] === Infinity ? -1 : dp[dp.length - 1];
};

参考官方题解,发现最本质的关系其实是:

dp[i] = Math.min(dp[i - coins[0]], dp[i - coins[1]], ..., dp[i - coins[j]]) + 1

每次做选择时,我的原始思路是遍历所有可能的金额选择,但更简单的做法是只从coins 中选择一种面额coins[j]的硬币,此时隐含的意思就是选择了一枚硬币(这就是上述状态转移方程最后的+ 1的意义),选择该面额硬币时的最优解(注意前提是选择该硬币)就应该是dp[i - j] + 1,枚举所有选择得出各种选择的最优解(即枚举coins)并取其最小值就是dp[i]的最优解,即dp[i] = Math.min(dp[i - coins[0]] + 1, dp[i - coins[1]] + 1, ..., dp[i - coins[j]] + 1),由于所有项都加了1,可以把1 提取出来,此时就和上述状态转移方程一致了。执行时间大幅缩减,优化后代码如下:

function coinChange(coins: number[], amount: number): number {
    const dp = [0];
    for (let i = 1; i <= amount; i++) {
        let min = Infinity;
        for (let c of coins) {
            if (i - c >= 0) {
                min = Math.min(min, dp[i - c] + 1);
                // console.log(i - c, min);
            }
        }
        dp[i] = min;
    }
    return dp[dp.length - 1] === Infinity ? -1 : dp[dp.length - 1];
};
1

回溯法:

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] helper = new int[amount];  
        return findWay(coins, amount, helper);
    }

    public int findWay(int[] coins, int amount, int[] helper){
        if(amount<0){
            return -1;
        }
        if(amount == 0){
            return 0;
        }
        if(helper[amount-1] != 0){ // 不等于0,则是已经计算过的
            return helper[amount-1];
        }
        int min = Integer.MAX_VALUE;
        for(int i = 0;i<coins.length;i++){
            int res = findWay(coins, amount-coins[i], helper);
            if(res>=0 && res < min){
                min = res + 1;
            }
        }
        helper[amount-1] = min == Integer.MAX_VALUE ? -1 : min;
        return helper[amount-1];
    }
}

dp:

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1]; 
        for(int i = 1;i<=amount;i++){
            int min = Integer.MAX_VALUE;
            for(int coin: coins){
                if(i>=coin && dp[i-coin] < min){
                    min = dp[i-coin] + 1;
                }
            }
            dp[i] = min;
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

从1-amount全算出来DP求解

class Solution {
public:
	vector<int> dp={0};
    int coinChange(vector<int> coins, int amount) {
		for(int i=1;i<=amount;i++)
		{
			int minc=65536;
			for(auto n:coins)
			{
				if(n<=i)
				minc=min(minc,dp[i-n]+1);
			}
			dp.push_back(minc);
		}
		return dp.back()==65536?-1:dp.back();
	}
};

一个贪心的解法,从大钱开始往小钱换

class Solution {
public:
    void helper(vector<int>& coins, int amount, int c_index, int count, int& ans) {
        if (amount == 0) {
            ans = min(ans, count);
            return;
        }
        if (c_index == coins.size()) return;

        for(int k = amount/coins[c_index]; k >= 0 && k + count < ans; --k) {
            helper(coins, amount - k * coins[c_index], c_index+1, count + k, ans);
        }
    }

    int coinChange(vector<int>& coins, int amount) {
        if (amount == 0) 
            return 0;
        sort(coins.rbegin(), coins.rend());
        int ans = INT_MAX;
        helper(coins, amount,0, 0, ans);
        return ans == INT_MAX ? -1 : ans;
    }
};

菜狗方法,更新找零表
dp 1 2 5
0 0 0 0
1 1 1 1
2 2 1 1
3 3 2 2
4 4 2 2
5 5 3 1
6 6 3 2
7 7 4 2
8 8 4 3
9 9 5 3
10 10 5 2
11 11 6 3