1、完全平方数
Q：给你一个整数n，返回和为n的完全平方数的最少数量。
完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9和16都是完全平方数，而3和11不是。
A ：
1、初始化：为了得到最少数量并且保证在更新时不会被初始数值影响，初始化全局为max；同时为了保证可以正常开始，（0，0）要重新赋值为0；
2、更新时：将本体看作要将目标值n拆解为多个完全平方数之和，可以想象成我们要找到一个数组，数组之和为n；
如果当前遍历的整数（j）小于对应位置的完全平方数，则该位置的完全平方数无法作为该数组的元素；反之则可以加入，但是我们要对比加入该元素之后和不加入时哪个方案的元素数更少（因为即使和相同，可选择的完全平方数也有多种方案，我们要找到最小的那一个）。
3、遍历边界：对于x维度的遍历很好理解，我们需要从[1，m]中选择任意个；对于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、零钱兑换（518）
Q：给你一个整数数组coins表示不同面额的硬币，另给一个整数amount表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回0。假设每一种面额的硬币有无限个。
A：
1、其实核心思路和完全平方数是一样的，只不过把if的判断条件和每次减去的值换为了coins的元素；
2、区别在于这次要求的是可能出现的组合数，所以在初始化时要将dp[0][0]（目标值为0，coins.length == 0)的情况初始化为1；
3、二维空间中记录的是对应组合下总的组合数
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、组合总数（377）
Q：给你一个由不同整数组成的数组nums，和一个目标整数target。请你从nums中找出并返回总和为target的元素组合的个数。顺序不同的序列被视作不同的组合。
A：
1、初始化：总和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和0
Q：给你一个二进制字符串数组strs和两个整数m和n。请你找出并返回strs的最大子集的长度，该子集中最多有m个0和n个1。如果x的所有元素也是y的元素，集合x是集合y的子集。
A：
1、有三个维度：字符串长度、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]; } }
