首页
Python
Java
前端
数据库
Linux
Chatgpt专题
开发者工具箱
lc518专题
9.12零钱兑换(LC518-M)(开始完全背包,与01背包的不同仅在于遍历顺序)
算法: 这是一道典型的背包问题,一看到钱币数量不限,就知道这是一个完全背包。 但本题和纯完全背包不一样,纯完全背包是凑成背包最大价值是多少,而本题是要求凑成总金额的物品组合个数! 动规五步曲: 1.确定dp数组以及下标: dp[j]:凑成总金额j的货币组合数为dp[j] 2.确定dp公式 dp[j] 就是所有的dp[j - coins[i]](考虑coins[i]的情况)相加
阅读更多...