1、完全平方数Q给你一个整数n返回和为n的完全平方数的最少数量。完全平方数是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9和16都是完全平方数而3和11不是。A 1、初始化为了得到最少数量并且保证在更新时不会被初始数值影响初始化全局为max同时为了保证可以正常开始00要重新赋值为02、更新时将本体看作要将目标值n拆解为多个完全平方数之和可以想象成我们要找到一个数组数组之和为n如果当前遍历的整数j小于对应位置的完全平方数则该位置的完全平方数无法作为该数组的元素反之则可以加入但是我们要对比加入该元素之后和不加入时哪个方案的元素数更少因为即使和相同可选择的完全平方数也有多种方案我们要找到最小的那一个。3、遍历边界对于x维度的遍历很好理解我们需要从[1m]中选择任意个对于y维度可能出现的和的区间为[0,n]刚开始没有任何元素加入时为0。4、二维空间中记录的是对应组合下最少的完全平方数class Solution { public int numSquares(int n) { int m (int) Math.sqrt(n); int[][] dp new int[m 1][n 1]; // 初始化 for(int[] r : dp) Arrays.fill(r, Integer.MAX_VALUE / 2); dp[0][0] 0; for(int i 1; i m; i){ for(int j 0; j n; j){ if(j i * i){ dp[i][j] dp[i - 1][j]; }else{ dp[i][j] Math.min(dp[i - 1][j], dp[i][j - i * i] 1); } } } return dp[m][n]; } }2、零钱兑换518Q给你一个整数数组coins表示不同面额的硬币另给一个整数amount表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额返回0。假设每一种面额的硬币有无限个。A1、其实核心思路和完全平方数是一样的只不过把if的判断条件和每次减去的值换为了coins的元素2、区别在于这次要求的是可能出现的组合数所以在初始化时要将dp[0][0]目标值为0coins.length 0)的情况初始化为13、二维空间中记录的是对应组合下总的组合数class Solution { public int coinChange(int[] coins, int amount) { int n coins.length; int[][] dp new int[n 1][amount 1]; for(int[] r : dp) Arrays.fill(r, Integer.MAX_VALUE / 2); dp[0][0] 0; for(int i 0; i n; i){ for(int j 0; j amount; j){ if(j coins[i]) dp[i 1][j] dp[i][j]; else dp[i 1][j] Math.min(dp[i 1][j - coins[i]] 1, dp[i][j]); } } return dp[n][amount] Integer.MAX_VALUE / 2 ? -1 : dp[n][amount]; } }3、组合总数377Q给你一个由不同整数组成的数组nums和一个目标整数target。请你从nums中找出并返回总和为target的元素组合的个数。顺序不同的序列被视作不同的组合。A1、初始化总和0任意前j个数字都有1种方案空序列2、根据标红部分要求要考虑顺序问题所以要先遍历target再遍历nums【先遍历 target总和 i、内层遍历 nums 数字是为了统计有序排列题目 377 要求[1,2]和[2,1]算两种不同方案 如果反过来先遍历物品再遍历金额只能统计无序组合】3、dp[i-num][n]取全部数字能凑出i-num的所有有序排列保证num可以拼接在任何顺序的序列末尾以此区分[1,2]和[2,1] 如果写成dp[i-num][j]只能用前j个数字会丢失排列、变成无序组合4、if分支区别于以上问题需要先赋给当前位置一个初始的组合上一个遍历结果之后再判断这个新的元素能不能放进去【错误做法】if(nums[j] i){ dp[i][j 1] dp[i][j]; }else{ dp[i][j 1] dp[i - nums[j]][n]; }这样会造成如果可以选当前元素会在初始为0的基础上加上这个元素这里是错的如果不选会继承上一个结果。class Solution { public int combinationSum4(int[] nums, int target) { int n nums.length; int[][] dp new int[target 1][n 1]; // 总和0任意前j个数字都有1种方案空序列 for(int i 0; i n;i) dp[0][i] 1; for(int i 0; i target; i){ for(int j 0; j n; j){ dp[i][j 1] dp[i][j]; if(nums[j] i){ dp[i][j 1] dp[i - nums[j]][n]; } } } return dp[target][n]; } }4、1和0Q给你一个二进制字符串数组strs和两个整数m和n。请你找出并返回strs的最大子集的长度该子集中最多有m个0和n个1。如果x的所有元素也是y的元素集合x是集合y的子集。A1、有三个维度字符串长度、0的个数、1的个数初始化时可以史记为三维或者二维个人倾向于二维优化一个维度空间会更好理解在这里显然是优化字符串2、统计遍历到的每隔字符串的0、1含量并将其作为m、n的下限继续下面的遍历如果不符合也就不必继续了如果符合且选择要加入这个字符串就将对应位置1并更新当前位置最大子集长度。class Solution { public int findMaxForm(String[] strs, int m, int n) { int[][] dp new int[m 1][n 1]; for(String s : strs){ char[] ch s.toCharArray(); int cntm 0; int cntn 0; for(char c : ch){ if(c 0) cntm; else cntn; } for(int j m; j cntm; j--){ for(int k n; k cntn; k--){ dp[j][k] Math.max(dp[j][k], dp[j - cntm][k - cntn] 1); } } } return dp[m][n]; } }
1、完全平方数Q给你一个整数n返回和为n的完全平方数的最少数量。完全平方数是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9和16都是完全平方数而3和11不是。A 1、初始化为了得到最少数量并且保证在更新时不会被初始数值影响初始化全局为max同时为了保证可以正常开始00要重新赋值为02、更新时将本体看作要将目标值n拆解为多个完全平方数之和可以想象成我们要找到一个数组数组之和为n如果当前遍历的整数j小于对应位置的完全平方数则该位置的完全平方数无法作为该数组的元素反之则可以加入但是我们要对比加入该元素之后和不加入时哪个方案的元素数更少因为即使和相同可选择的完全平方数也有多种方案我们要找到最小的那一个。3、遍历边界对于x维度的遍历很好理解我们需要从[1m]中选择任意个对于y维度可能出现的和的区间为[0,n]刚开始没有任何元素加入时为0。4、二维空间中记录的是对应组合下最少的完全平方数class Solution { public int numSquares(int n) { int m (int) Math.sqrt(n); int[][] dp new int[m 1][n 1]; // 初始化 for(int[] r : dp) Arrays.fill(r, Integer.MAX_VALUE / 2); dp[0][0] 0; for(int i 1; i m; i){ for(int j 0; j n; j){ if(j i * i){ dp[i][j] dp[i - 1][j]; }else{ dp[i][j] Math.min(dp[i - 1][j], dp[i][j - i * i] 1); } } } return dp[m][n]; } }2、零钱兑换518Q给你一个整数数组coins表示不同面额的硬币另给一个整数amount表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额返回0。假设每一种面额的硬币有无限个。A1、其实核心思路和完全平方数是一样的只不过把if的判断条件和每次减去的值换为了coins的元素2、区别在于这次要求的是可能出现的组合数所以在初始化时要将dp[0][0]目标值为0coins.length 0)的情况初始化为13、二维空间中记录的是对应组合下总的组合数class Solution { public int coinChange(int[] coins, int amount) { int n coins.length; int[][] dp new int[n 1][amount 1]; for(int[] r : dp) Arrays.fill(r, Integer.MAX_VALUE / 2); dp[0][0] 0; for(int i 0; i n; i){ for(int j 0; j amount; j){ if(j coins[i]) dp[i 1][j] dp[i][j]; else dp[i 1][j] Math.min(dp[i 1][j - coins[i]] 1, dp[i][j]); } } return dp[n][amount] Integer.MAX_VALUE / 2 ? -1 : dp[n][amount]; } }3、组合总数377Q给你一个由不同整数组成的数组nums和一个目标整数target。请你从nums中找出并返回总和为target的元素组合的个数。顺序不同的序列被视作不同的组合。A1、初始化总和0任意前j个数字都有1种方案空序列2、根据标红部分要求要考虑顺序问题所以要先遍历target再遍历nums【先遍历 target总和 i、内层遍历 nums 数字是为了统计有序排列题目 377 要求[1,2]和[2,1]算两种不同方案 如果反过来先遍历物品再遍历金额只能统计无序组合】3、dp[i-num][n]取全部数字能凑出i-num的所有有序排列保证num可以拼接在任何顺序的序列末尾以此区分[1,2]和[2,1] 如果写成dp[i-num][j]只能用前j个数字会丢失排列、变成无序组合4、if分支区别于以上问题需要先赋给当前位置一个初始的组合上一个遍历结果之后再判断这个新的元素能不能放进去【错误做法】if(nums[j] i){ dp[i][j 1] dp[i][j]; }else{ dp[i][j 1] dp[i - nums[j]][n]; }这样会造成如果可以选当前元素会在初始为0的基础上加上这个元素这里是错的如果不选会继承上一个结果。class Solution { public int combinationSum4(int[] nums, int target) { int n nums.length; int[][] dp new int[target 1][n 1]; // 总和0任意前j个数字都有1种方案空序列 for(int i 0; i n;i) dp[0][i] 1; for(int i 0; i target; i){ for(int j 0; j n; j){ dp[i][j 1] dp[i][j]; if(nums[j] i){ dp[i][j 1] dp[i - nums[j]][n]; } } } return dp[target][n]; } }4、1和0Q给你一个二进制字符串数组strs和两个整数m和n。请你找出并返回strs的最大子集的长度该子集中最多有m个0和n个1。如果x的所有元素也是y的元素集合x是集合y的子集。A1、有三个维度字符串长度、0的个数、1的个数初始化时可以史记为三维或者二维个人倾向于二维优化一个维度空间会更好理解在这里显然是优化字符串2、统计遍历到的每隔字符串的0、1含量并将其作为m、n的下限继续下面的遍历如果不符合也就不必继续了如果符合且选择要加入这个字符串就将对应位置1并更新当前位置最大子集长度。class Solution { public int findMaxForm(String[] strs, int m, int n) { int[][] dp new int[m 1][n 1]; for(String s : strs){ char[] ch s.toCharArray(); int cntm 0; int cntn 0; for(char c : ch){ if(c 0) cntm; else cntn; } for(int j m; j cntm; j--){ for(int k n; k cntn; k--){ dp[j][k] Math.max(dp[j][k], dp[j - cntm][k - cntn] 1); } } } return dp[m][n]; } }
