LeetCode 322 Coin Change

动态规划问题 2022-02-14 12:52:52 2022-02-14 18:25:57 236 次浏览

概述

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];
    }
};

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