LeetCode 518 Coin Change 2

概述

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

动态规划法

dp[s][i] 代表从数组的第 i 个开始，凑成 s 个方式个数。

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<vector<int>> dp(amount + 1, vector<int>(coins.size(), -1));
        return helper(coins, dp, amount, 0);
    }
    
    int helper(vector<int>& coins, vector<vector<int>>& dp, int s, int i) {
        if (s == 0) return 1;
        if (i >= coins.size()) return 0;
        if (dp[s][i] != -1) return dp[s][i];
        dp[s][i] = 0;
        int c = 0;
        while (c <= s) {
            dp[s][i] += helper(coins, dp, s - c, i + 1);
            c += coins[i];
        }
        return dp[s][i];
    }
};

Links: leetcode-518-coin-change-2

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