在哪注册网站,一个做智能化的网站有哪些,赣州app开发公司,浮雕模东莞网站建设题目#xff1a;
链接#xff1a;LeetCode 518. 零钱兑换 II 难度#xff1a;中等
动态规划#xff1a;
dp[i][j] 定义#xff1a;可选前 i 种硬币的情况下#xff0c;组成金额 j 的组合数。 初始状态#xff1a;
dp[0][j] 0, 1 j amount#xff08;不选…题目
链接LeetCode 518. 零钱兑换 II 难度中等
动态规划
dp[i][j] 定义可选前 i 种硬币的情况下组成金额 j 的组合数。 初始状态
dp[0][j] 0, 1 j amount不选取任何硬币的情况下组成正整数金额的组合数为0dp[i][0] 1, 0 i n金额为0的情况下只有空集的这一种组合才是0
状态转移方程 if(j - coins[i - 1] 0) // 容量足够选取该硬币组合数选取该硬币和不选该硬币两种状态相加dp[i][j] dp[i][j - coins[i - 1]] dp[i - 1][j];elsedp[i][j] dp[i - 1][j]; // 容量不足以选取该硬币组合数不选该硬币的组合数代码
class Solution {
public:int change(int amount, vectorint coins) {int n coins.size();vectorvectorint dp(n 1, vectorint(amount 1, 0)); // dp[i][j]i代表使用前i种硬币j代表金额for(int i 0; i n; i) // 初始化组成金额为0的方案数总是1不选任何硬币dp[i][0] 1;for(int i 1; i n; i){for(int j 1; j amount; j){if(j - coins[i - 1] 0) // 容量足够选取该硬币组合数选取该硬币和不选该硬币两种状态相加dp[i][j] dp[i][j - coins[i - 1]] dp[i - 1][j];elsedp[i][j] dp[i - 1][j]; // 容量不足以选取该硬币组合数不选该硬币的组合数}}return dp[n][amount];}
};时间复杂度O(N * amount)N是coins数组长度。 空间复杂度O(N * amount)。
