这里记录刷hot100的思考过程详解方便后续记忆复习。动态规划的核心是找状态找局部状态然后组建成整体状态。题号7070. 爬楼梯假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢具体题解class Solution { public int climbStairs(int n) { int p0,q0,r1; for(int i0;in;i){ pq; qr; rpq; } return r; } }思路解析确定初始状态下一状态可以由前两个状态实现。使用滚动存储的方式。必会知识无题号118118. 杨辉三角给定一个非负整数numRows生成「杨辉三角」的前numRows行。在「杨辉三角」中每个数是它左上方和右上方的数的和。具体题解class Solution { public ListListInteger generate(int numRows) { ListListInteger ans new ArrayList(); for(int i0;inumRows;i){ ListInteger tmpnew ArrayList(); for(int j0;ji;j){ if(i0||j0||ji){ tmp.add(1); }else{ tmp.add(ans.get(i-1).get(j)ans.get(i-1).get(j-1)); } } ans.add(tmp); } return ans; } }思路解析下一状态可以又上一状态组成。在这里需要处理边界情况。必会知识无题号198198. 打家劫舍你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你不触动警报装置的情况下一夜之内能够偷窃到的最高金额。具体题解class Solution { public int rob(int[] nums) { int ans0; int nnums.length; int[] tmpnew int[n]; if(nums.length1){ return nums[0]; } tmp[0]nums[0];tmp[1]Math.max(nums[0],nums[1]); for(int i2;in;i){ tmp[i]Math.max(tmp[i-1],tmp[i-2]nums[i]); } return Math.max(tmp[n-2],tmp[n-1]); } }思路解析和题号70非常类似。当前状态又前两个状态决定确定好初始状态就可以了必会知识无题号279279. 完全平方数给你一个整数n返回和为n的完全平方数的最少数量。完全平方数是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9和16都是完全平方数而3和11不是。具体题解class Solution { public int numSquares(int n) { int[] findnew int[n1]; for(int i1;in;i){ find[i]Integer.MAX_VALUE; for(int j1;j*ji;j){ find[i]Math.min(find[i-j*j],find[i]); } find[i]find[i]1; } return find[n]; } }思路解析前面都是通过滚动存储的方式去迭代下一个状态这里就引入dp数组了。从小数开始迭代到最终结果。必会知识无题号322322. 零钱兑换给你一个整数数组coins表示不同面额的硬币以及一个整数amount表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回-1。你可以认为每种硬币的数量是无限的。具体题解class Solution { public int coinChange(int[] coins, int amount) { if(amount0) return 0; int[] fnew int[amount1]; for(int i1;iamount;i){ int minInteger.MAX_VALUE; int tmp0; for(int j0;jcoins.length;j){ if(i-coins[j]0) continue; if(f[i-coins[j]]-1) continue; minMath.min(min,f[i-coins[j]]); tmp1; } if(tmp0){ f[i]-1; }else{ f[i]min1; } } return f[amount]; } }思路解析与题号279思路一致但要处理无法兑换零钱的情况。必会知识无题号139139. 单词拆分相关企业给你一个字符串s和一个字符串列表wordDict作为字典。如果可以利用字典中出现的一个或多个单词拼接出s则返回true。注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。具体题解class Solution { public boolean wordBreak(String s, ListString wordDict) { SetString hashsetnew HashSet(wordDict); boolean dp[] new boolean[s.length()1]; dp[0]true; for(int i1;is.length()1;i){ for(int j0;ji;j){ if(dp[j]hashset.contains(s.substring(j,i))){ dp[i]true; break; } } } return dp[s.length()]; } }思路解析这里dp的下标代表什么要注意清楚这里代表的到第i个的字母的字符串是否可被组成。必会知识list集合直接转set集合。直接传入构造参数。题号300300. 最长递增子序列给你一个整数数组nums找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。具体题解class Solution { public int lengthOfLIS(int[] nums) { int[] dpnew int[nums.length1]; dp[0]0; dp[1]1; int ans1; if(nums.length0){ return 0; } for(int i2;inums.length1;i){ int max0; for(int j1;ji;j){ if(nums[i-1]nums[j-1]){ maxMath.max(max,dp[j]); } } dp[i]max1; ansMath.max(ans,dp[i]); } return ans; } }思路解析类似于题号139.明确dp数组为到第i个数的最大递增序列长度。如果当前第i个元素大于前面某个元素那前面某个元素对应的最大递增序列长度可以1max可能被更新。必会知识无题号152152. 乘积最大子数组给你一个整数数组nums请你找出数组中乘积最大的非空连续 子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。测试用例的答案是一个32-位整数。请注意一个只包含一个元素的数组的乘积是这个元素的值。具体题解class Solution { public int maxProduct(int[] nums) { int ansnums[0]; int MaxFnums[0],MinFnums[0]; for(int i1;inums.length;i){ int mxMaxF,mnMinF; MaxFMath.max(Math.max(nums[i],mx*nums[i]),mn*nums[i]); MinFMath.min(Math.min(nums[i],mx*nums[i]),mn*nums[i]); ansMath.max(ans,MaxF); } return ans; } }思路解析到第i个数的最大值可能被更新为该值mx*nums[i]mn*nums[i]。这里采用的滚动存储的方式不断计算下一个值可能出现的最大值用来更新ans。必会知识无题号416416. 分割等和子集给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。具体题解class Solution { public boolean canPartition(int[] nums) { int sum0; for(int i0;inums.length;i){ sumnums[i]; } if(sum%21){ return false; } int targetsum/2; boolean[] dpnew boolean[target1]; dp[0]true; for(int i0;inums.length;i){ int numnums[i]; for(int jtarget;jnum;j--){ dp[j]dp[j]||dp[j-num]; } } return dp[target]; } }思路解析在将sum拆分为target后和题号322很类似。不断遍历数组中的数去看看j-num是否能被构造出来。nums数组中所有元素随便组合可以构造的状态是否和我要找的状态target有重合。必会知识无题号3232. 最长有效括号给你一个只包含(和)的字符串找出最长有效格式正确且连续括号 子串 的长度。左右括号匹配即每个左括号都有对应的右括号将其闭合的字符串是格式正确的比如(()())。具体题解class Solution { public int longestValidParentheses(String s) { int maxans0; int[] dpnew int[s.length()]; for(int i1;is.length();i){ if(s.charAt(i))){ if(s.charAt(i-1)(){ dp[i]2(i2?dp[i-2]:0); }else if(i-dp[i-1]-10s.charAt(i-dp[i-1]-1)(){ dp[i]dp[i-1]2(i-dp[i-1]-20?dp[i-dp[i-1]-2]:0); } maxansMath.max(dp[i],maxans); } } return maxans; } }思路解析和最长递增序列非常类似dp表示的是到第i个为止的最长有效括号。然后就是如何计算dp[i]的问题了。分情况讨论只有当遇到‘’时可能改变状态这点与最长递增序列也很类似。必会知识无接下来的多维动态规划要更模板一些题号62一个机器人位于一个m x n网格的左上角 起始点在下图中标记为 “Start” 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。问总共有多少条不同的路径具体题解class Solution { public int uniquePaths(int m, int n) { int[][] dpsnew int[m][n]; dps[0][0]1; for(int i0;idps.length;i){ for(int j0;jdps[0].length;j){ if(i0j0){ continue; } dps[i][j](i-10?dps[i-1][j]:0)(j-10?dps[i][j-1]:0); } } return dps[m-1][n-1]; } }思路解析可以选择数学公式计算也可以使用动态规划。当前位置只能从上面或左边位置到达。必会知识无题号6464. 最小路径和给定一个包含非负整数的mxn网格grid请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。说明每次只能向下或者向右移动一步。具体题解class Solution { public int minPathSum(int[][] grid) { int mgrid.length;int ngrid[0].length; int[][] dpsnew int[m][n]; dps[0][0]grid[0][0]; for(int i0;im;i){ for(int j0;jn;j){ if(i0j0){ continue; } dps[i][j]grid[i][j] Math.min((i-10?dps[i-1][j]:Integer.MAX_VALUE),(j-10?dps[i][j-1]:Integer.MAX_VALUE)); } } return dps[m-1][n-1]; } }思路解析和不同路径几乎一模一样。必会知识无题号55. 最长回文子串给你一个字符串s找到s中最长的 回文 子串。具体题解class Solution { public String longestPalindrome(String s) { int ns.length(); int ans1; int left0,right0; boolean[][] findnew boolean[n][n]; for(int i0;in;i){ Arrays.fill(find[i],true); } for(int in-2;i0;i--){ for(int ji1;jn;j){ find[i][j] (s.charAt(i) s.charAt(j)) find[i1][j-1]; if(find[i][j]){ if(j-i1ans){ ansj-i1; lefti; rightj; } } } } return s.substring(left,right1); } }class Solution { public String longestPalindrome(String s) { if(snull||s.length()0){ return ; } int start0,end0; for(int i0;is.length();i){ int len1expandAroundCenter(s,i,i); int len2expandAroundCenter(s,i,i1); int lenMath.max(len1,len2); if(lenend-start){ starti-(len-1)/2; endilen/2; } } return s.substring(start,end1); } public int expandAroundCenter(String s,int left,int right){ while(left0rights.length()s.charAt(left)s.charAt(right)){ left--; right; } return right-left-1; } }思路解析有两种思路一是动态规划遍历每个元素从中间往外扩展看看最远到哪里。二是利用回溯算法中分割回文串记录哪两个位置是回文串的方法。必会知识题号11431143. 最长公共子序列给定两个字符串text1和text2返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列返回0。一个字符串的子序列是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。例如ace是abcde的子序列但aec不是abcde的子序列。两个字符串的公共子序列是这两个字符串所共同拥有的子序列。具体题解class Solution { public int longestCommonSubsequence(String text1, String text2) { int mtext1.length(),ntext2.length(); int[][] dpsnew int[m][n]; for(int i0;im;i){ char ch1text1.charAt(i); for(int j0;jn;j){ char ch2text2.charAt(j); if(ch1ch2){ dps[i][j](i-10j-10?dps[i-1][j-1]:0)1; }else{ dps[i][j]Math.max(i0?dps[i-1][j]:0,j0?dps[i][j-1]:0); } } } return dps[m-1][n-1]; } }思路解析依旧是“最长”问题只能一维变成了二维。二层循环遍历去从局部推整体。必会知识无题号7272. 编辑距离给你两个单词word1和word2请返回将word1转换成word2所使用的最少操作数。你可以对一个单词进行如下三种操作插入一个字符删除一个字符替换一个字符具体题解class Solution { public int minDistance(String word1, String word2) { int nword1.length(); int mword2.length(); if(n*m0){ return nm; } int[][] dpsnew int[n1][m1]; for(int i0;in1;i){ dps[i][0]i; } for(int j0;jm1;j){ dps[0][j]j; } for(int i1;in1;i){ for(int j1;jm1;j){ int insdps[i][j-1]1; int deldps[i-1][j]1; int spldps[i-1][j-1]; if(word1.charAt(i-1)!word2.charAt(j-1)){ splspl1; } dps[i][j]Math.min(Math.min(ins,del),spl); } } return dps[n][m]; } }思路解析下标为第i个字母。通过之前状态记录当前状态最后一步如果是插入删除增添分别对应的最小步骤数必会知识无