LeetCode 322 Coin Change

概述

https://leetcode.com/problems/coin-change/

动态规划法（递归法）

1. base case：剩余签署为 0 时需要 0 个硬币
2. 状态：剩余钱数
3. 选择：从升序排列的硬币中选一个小于等于的。
4. dp 函数 / 数组的定义：dp[剩余钱数] = 需要的硬币数

代码：

class Solution {
public:
    vector<int>* dp;
    vector<int>* coins;
    int coinChange(vector<int>& coins, int amount) {
        dp = new vector<int>(amount + 1, INT_MAX);
        (*dp)[0] = 0;
        sort(coins.begin(), coins.end());
        this->coins = &coins;
        return helper(amount);
    }
    
    int helper(int n) {
        if ((*dp)[n] != INT_MAX) return (*dp)[n];
        int minN = INT_MAX;
        for (auto c : *coins) {
            if (c > n) break;
            int num = helper(n - c);
            if (num != -1) minN = min(minN, 1 + num);
        }
        if (minN == INT_MAX) minN = -1;
        (*dp)[n] = minN;
        return minN;
    }
};

动态规划法（迭代法）

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        sort(coins.begin(), coins.end());
        for (int i = 1; i <= amount; i ++) {
            for (auto c : coins) {
                if (c > i) break;
                if (dp[i-c] != -1) dp[i] = min(dp[i], 1 + dp[i-c]);
            }
            if (dp[i] == INT_MAX) dp[i] = -1;
        }
        return dp[amount];
    }
};

Links: leetcode-322-coin-change

未经允许，禁止转载，本文源站链接：https://iamazing.cn/