08.11硬币（完全背包问题）
2020-12-16 本文已影响0人
棉花糖7
已经快2个月没有刷过题了，想重新拾起来可真是太不容易了，之前会的，现在都不会了。
这是一道完全背包问题，自己又是卡了好几小时，想不出来。
第一种方法是用二维数组，dp[i][j] 表示的是用前i种硬币凑出总金额为 j 的最大可能性
第二种方法是降维，因为从状态转移方程可以看出，dp[i][j] 仅仅和 dp[i-1]的状态有关，所以可以压缩为 1 维
题目
二维
一维
另解
也即一维的另外一种理解方式
