网站建设课后心得,海外推广品牌,网站建设金思扬网络,安徽农垦建设工程信息网322. 零钱兑换
动规五部曲分析如下#xff1a; 确定dp数组以及下标的含义 dp[j]#xff1a;凑足总额为j所需钱币的最少个数为dp[j] 确定递推公式 凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]#xff0c;那么只需要加上一个钱币coins[i]即dp[j - coins[i]] 1就是…322. 零钱兑换
动规五部曲分析如下 确定dp数组以及下标的含义 dp[j]凑足总额为j所需钱币的最少个数为dp[j] 确定递推公式 凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]那么只需要加上一个钱币coins[i]即dp[j - coins[i]] 1就是dp[j]考虑coins[i]
所以dp[j] 要取所有 dp[j - coins[i]] 1 中最小的。
递推公式dp[j] min(dp[j - coins[i]] 1, dp[j]);
dp数组如何初始化 首先凑足总金额为0所需钱币的个数一定是0那么dp[0] 0;
其他下标对应的数值呢
考虑到递推公式的特性dp[j]必须初始化为一个最大的数否则就会在min(dp[j - coins[i]] 1, dp[j])比较的过程中被初始值覆盖。
所以下标非0的元素都是应该是最大值。
确定遍历顺序 本题求钱币最小个数那么钱币有顺序和没有顺序都可以都不影响钱币的最小个数。
所以本题并不强调集合是组合还是排列。
如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品。
/*** param {number[]} coins* param {number} amount* return {number}*/
var coinChange function (coins, amount) {const dp Array(amount 1).fill(Infinity)dp[0] 0for (let i 1; i amount; i) {for (let j 0; j coins.length; j) {if (i coins[j] dp[i - coins[j]] ! Infinity) {dp[i] Math.min(dp[i], dp[i - coins[j]] 1)}}}return dp[amount] Infinity ? -1 : dp[amount]
};279. 完全平方数 确定dp数组dp table以及下标的含义 dp[j]和为j的完全平方数的最少数量为dp[j] 确定递推公式 dp[j] 可以由dp[j - i * i]推出 dp[j - i * i] 1 便可以凑成dp[j]。
此时我们要选择最小的dp[j]所以递推公式dp[j] min(dp[j - i * i] 1, dp[j]);
dp数组如何初始化 dp[0]表示 和为0的完全平方数的最小数量那么dp[0]一定是0。
有同学问题那0 * 0 也算是一种啊为啥dp[0] 就是 0呢
看题目描述找到若干个完全平方数比如 1, 4, 9, 16, …题目描述中可没说要从0开始dp[0]0完全是为了递推公式。
非0下标的dp[j]应该是多少呢
从递归公式dp[j] min(dp[j - i * i] 1, dp[j]);中可以看出每次dp[j]都要选最小的所以非0下标的dp[j]一定要初始为最大值这样dp[j]在递推的时候才不会被初始值覆盖。
确定遍历顺序 我们知道这是完全背包
如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品。
/*** param {number} n* return {number}*/
var numSquares function (n) {let dp new Array(n 1).fill(Infinity)dp[0] 0for (let i 1; i n; i) {for (let j 1; j * j i; j) {dp[i] Math.min(dp[i - j * j] 1, dp[i])}}return dp[n]
};
