算法题（动态规划）

一、题目1、完全平方数LC 2792、零钱兑换LC 322二、题解1、完全平方数LC 2791分析要求用最少的完全平方数比如 1、4、9 等相加得到给定数字 n是一个典型的最小数量选择问题都是求 “最少个数”可以选择用记忆化深度优先搜索 来做。把问题转化成一个递归选择问题对于每一个平方数我们可以选择用它或者不用它然后在所有合法方案里取数量最少的那一个。先把最大可能用到的平方数的平方根算出来比如 n12最大平方数是 9平方根就是 3这样递归时就知道要考虑哪些数字。递归函数里有两个关键参数i 表示当前考虑到第几个平方数j 表示当前还需要凑出的数字。递归的边界很清晰如果 i 等于 0说明已经没有平方数可以选了这时候如果 j 也等于 0就代表成功凑出来返回 0否则返回一个很大的值表示方案不合法。为了避免大量重复递归导致超时可以用一个 memo 数组记录已经算过的状态数组里存的是对应状态下需要的最少平方数个数。如果某个状态已经算过就直接返回结果不用再重复递归。在递归过程中如果当前剩余数字 j 比当前平方数还小那就不能选这个平方数只能跳过考虑下一个。如果可以选就分两种情况不选当前平方数直接递归下一个或者选当前平方数用掉它之后继续递归两种方案取最小值。2解答class Solution { static int[][] memo new int[101][10001]; //每种情况所需个数 meno[3][12]表示对12这个数用1、4、9需要多少个 static { for(int[] row : memo){ Arrays.fill(row,-1); //初始化为-1表示没有计算过 } } public int numSquares(int n) { return dfs((int)Math.sqrt(n), n); } public int dfs(int i, int j){ if(i 0){ return j 0 ? 0 : Integer.MAX_VALUE/2; //边界i0,j0,返回0如果j不为0说明不合法 } if(memo[i][j] ! -1){ return memo[i][j]; } if(j i*i){ return memo[i][j] dfs(i - 1, j); //不选择当前平方数考虑下一个 } return memo[i][j] Math.min(dfs(i-1, j), dfs(i, j - i*i)1); //选择和不选择的情况选取个数最小的 } }2、零钱兑换LC 3221分析用最少数量的硬币凑出指定金额和完全平方数几乎是同一个模型同样使用了记忆化 DFS来实现。思路是对每一种硬币做两种选择要么不使用当前硬币要么使用它然后在两种选择里取硬币数量最少的那一个。递归函数有两个关键参数i 表示当前处理到第几个硬币c 表示还需要凑多少钱。这样每一步都在缩小问题规模直到到达边界。递归的边界条件如果 i 小于 0说明已经没有硬币可以选了这时候如果 c 等于 0就代表凑成了返回 0否则返回一个较大的值表示方案无效。使用一个二维 memo 数组记录已经算过的状态只要算过就直接读取结果不再重复递归。在递归过程中如果当前需要凑的钱比硬币面值还小那就不能选这个硬币只能跳过。如果可以选就比较两种方案不选当前硬币直接递归下一个或者选当前硬币金额减少后继续递归并且硬币数加一。两种方案取最小值。最后判断结果是否有效有效就返回无效返回 - 1。2解答class Solution { public int coinChange(int[] coins, int amount) { int n coins.length; int[][] memo new int[n][amount 1]; for (int[] row : memo) { Arrays.fill(row, -1); // -1 表示没有计算过 } int ans dfs(n - 1, amount, coins, memo); return ans Integer.MAX_VALUE / 2 ? ans : -1; } private int dfs(int i, int c, int[] coins, int[][] memo) { if (i 0) { return c 0 ? 0 : Integer.MAX_VALUE / 2; // 除 2 防止下面 1 溢出 } if (memo[i][c] ! -1) { // 之前计算过 return memo[i][c]; } if (c coins[i]) { // 只能不选 return memo[i][c] dfs(i - 1, c, coins, memo); } // 不选 vs 继续选 return memo[i][c] Math.min(dfs(i - 1, c, coins, memo), dfs(i, c - coins[i], coins, memo) 1); } }