https://leetcode.cn/problems/coin-change-ii/description/
可以直接考虑用完全背包的传统二维做法
class Solution {
public int change(int amount, int[] coins) {
// 题意就是一个完全背包问题
// f[i][j]表示前i个数中选,体积等于j的最大选法种数,答案就是f[n][amount]
// 以第i个数选多少个来划分子集
// f[i][j] = f[i-1][j] + f[i][j-conis[i]]
// f[0][0]=1; // 初值,只有一种选法
int N = 310;
int[][] f=new int[N][5010];
f[0][0]=1; // 什么也不选也是一种选法
for(int i=1;i<=coins.length;i++)
for(int j=0;j<=amount;j++)
{
// 这里coins需要偏移一位
if(j>=coins[i-1])f[i][j]=f[i-1][j]+f[i][j-coins[i-1]];
else f[i][j]=f[i-1][j];
}
return f[coins.length][amount];
}
}
标签:int,coins,选法,II,518,amount,leetcode From: https://www.cnblogs.com/lxl-233/p/18394924