LeetCode 518 Coin Change 2

标签: 动态规划问题 LeetCode 发布于:2022-02-17 16:37:15 编辑于:2022-02-19 13:11:50 浏览量:1053

概述

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

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