Leetcode|完全背包|322. 零钱兑换

SL_World

发布于 2021-09-18 16:39:37

2970

发布于 2021-09-18 16:39:37

文章被收录于专栏：X

1 动态规划（完全背包）

实际状态转移方程如下：

dp[状态i] = min(1 + dp[状态i - 选择1], 1 + dp[状态i - 选择2], 1 + dp[状态i - 选择3],....);

其中，我们对多个元素求最小怎么求的？是不是下面这样

int maxNum = INT_MAX;
for (int i = 0; i < size; i++)
	maxNum = min(maxNum, num[i]);

所以就有了状态转移方程在程序中的主流表现形式

dp[状态i] = min(dp[状态i], 选择j);

完整代码如下

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        // 1.base case
        dp[0] = 0; 
        // 2.状态
        for (int i = 1; i <= amount; i++) 
            // 3.选择
            for (auto& coin : coins) {
                if (i < coin || dp[i - coin] == INT_MAX) continue; // 因为不能有INT_MAX + 1
                // 4.状态转移
                dp[i] = min(dp[i], 1 + dp[i - coin]);
            }
        return (dp[amount] == INT_MAX) ? -1 : dp[amount];
    }
};