01背包416. 分割等和子集 - 力扣LeetCode二维更容易理解dp 代表从0,i索引是否能组成target01背包初始化0行0列对于0列都为true因为target0默认不选对于0行拿到nums[0]恰好填满时候为true。所以dp[0][nums[0]]true如果没有越界递推公式对于当前nums[i]可以选择拿或者不拿取到一个或的结果。class Solution { public boolean canPartition(int[] nums) { // 类似01背包 int sum 0; for(int i 0; i nums.length; i){ sum nums[i]; } if(sum % 2 ! 0) return false; int target sum /2; // 从0,i上能否填满target boolean dp[][] new boolean[nums.length][target1]; // dp[i][j] dp[i-1][j] || dp[i-1][target-nums[i]] // 当target为0的时候都不选默认为true for(int i 0; i nums.length; i){ dp[i][0] true; } // 当i0的时候如果恰好填满target为true if(nums[0] target) dp[0][nums[0]]true; for(int i 1; i nums.length;i){ for(int j 1; j target; j){ dp[i][j] dp[i-1][j]; if(j-nums[i] 0){ dp[i][j] dp[i-1][j] || dp[i-1][j-nums[i]]; } } } return dp[nums.length-1][target]; } }完全背包322. 零钱兑换 - 力扣LeetCode完全背包先遍历物品内部遍历容量初始化的最大值注意按照1的最多数量1就可以出错的点容量错误用整数最大值会越界class Solution { public int coinChange(int[] coins, int amount) { int dp[] new int[amount1]; for(int i 1; i amount; i){ dp[i] amount1; } for(int i 0; i coins.length;i){ for(int j 1; j amount;j){ if(j - coins[i] 0){ dp[j] Math.min(dp[j], dp[j-coins[i]]1); } } } if(dp[amount] amount1) return -1; return dp[amount]; } }279. 完全平方数 - 力扣LeetCode完全背包的变种和零钱兑换几乎一样先遍历物品此时物品是i*i平方数内部正序循环容量初始化都用容量1.class Solution { public int numSquares(int n) { int dp [] new int[n1]; dp[0]0; for(int i1; in;i){ dp[i]n1; } for(int i 1; i * i n;i){ int sq i * i; for(int j 1; j n;j){ if(j sq){ dp[j] Math.min(dp[j], dp[j - sq] 1); } } } return dp[n]; } }139. 单词拆分 - 力扣LeetCode类似完全背包但是不能套用外层遍历物品的模板字符串位置问题一般是先遍历容量推理定义前i个字符能否拆分要看前j个能否拆分[j,i]是否是一个单词初始化前0个为true。公式要算dp[i]就把所有j i试一遍看dp[j] s[j..i-1]是否成立。只要有一个成立dp[i]就为true。算dp[i]时前面所有dp[0..i-1]都已经算好直接查表复用。不是只复用dp[i-1]。class Solution { public boolean wordBreak(String s, ListString wordDict) { // 从前i个字符串能否被worddict填满。 // dp[i] dp[j] s[j, i]; boolean dp[] new boolean[s.length()1]; dp[0]true; //在前i个字符每一种i的情况下只要有一种j可以成功切分dp[i]就是true所以找到了就break // 内层循环是为了尝试所有切分点让i可以拆分为j(j,i) for(int i 1; i s.length();i){ for(int j 0; j i;j){ if(dp[j] (wordDict.contains(s.substring(j,i)))){ dp[i]true; break; } } } return dp[s.length()]; } }连续子数组/子串”问题152. 乘积最大子数组 - 力扣LeetCodemaxdp[i]以i结尾的最大值mindp[i]以i结尾的最小值class Solution { public int maxProduct(int[] nums) { // dpmax[i] dpmin[i-1] * nums[i] if nums[i] 0 // dpmax[i] dpmax[i-1] * nums[i] if nums[i] 0 int maxdp [] new int[nums.length]; int mindp [] new int[nums.length]; maxdp[0] nums[0]; mindp[0]nums[0]; int result nums[0]; for(int i 1; i nums.length;i){ maxdp[i] Math.max(nums[i], Math.max(nums[i] * mindp[i-1], nums[i] * maxdp[i-1])); mindp[i] Math.min(nums[i], Math.min(nums[i] * maxdp[i-1], nums[i] * mindp[i-1])); result Math.max(result, maxdp[i]); } return result; } }32. 最长有效括号 - 力扣LeetCode推理方程dp[i] 以s[i]结尾的最长有效括号子串长度。初始化dp[0] 0因为一个字符形成不了其余也为0状态转移s[i](时为 0s[i])时若前一个是(则dp[i]dp[i-2]2否则跳过dp[i-1]看s[j]ji-dp[i-1]-1能否配对。答案取max(dp)全程用res记录。class Solution { public int longestValidParentheses(String s) { if(s.length()0)return 0; // 以i结尾的字符换的最长连续子串 int dp[]new int[s.length()]; dp[0]0; // 初始化 int res 0; for(int i 1; i s.length();i){ // i位置以(结尾必然无法拼接 if(s.charAt(i) (){ dp[i]0; continue; } if(s.charAt(i) )){ if(s.charAt(i-1)(){ if(i-20) { dp[i]2; }else{ dp[i] dp[i-2]2; } }else{ int j i-dp[i-1] -1; if(j-1 0 s.charAt(j) (){ dp[i] dp[i-1]2dp[j-1]; }else if(j 0 j1 s.charAt(j) (){ dp[i] dp[i-1]2; } } if(dp[i] res){ res dp[i]; } } } return res; } }300. 最长递增子序列 - 力扣LeetCode错误分析初始化没初始化全部数组推理方程以i位置结束的最大递增长度初始化所有dp位置初始为1.因为至少一个转移对于每个i,看他前面的所有j位置如果nums[j] nums[i]找到一种dp[i]的可能dp[j]1然后取dp[i]的最大值。class Solution { public int lengthOfLIS(int[] nums) { // i位置结尾的最大递增子序列是dp[i] int dp[] new int[nums.length]; Arrays.fill(dp,1); int resdp[0]; for(int i 1;inums.length;i){ for(int j 0; ji; j){ if(nums[i] nums[j]){ dp[i]Math.max(dp[i], dp[j]1); } } resMath.max(dp[i],res); } return res; } }总结01背包简化为一维数组之后外循环物品内循环容量逆序完全背包简化为一维数组之后外循环物品内循环容量正序连续子串/子数组或者扩展时需要看末尾元素的用“以 i 结尾”前缀的整体性质扩展时不关心末尾具体是谁的用“前 i 个”