62. 不同路径 - 力扣LeetCode公式为dp[i][j] dp[i-1][j]dp[i][j-1]初始化第一行第一列的值为1任意IJ位置可以由上面和左边加起来得到路径数量64. 最小路径和 - 力扣LeetCode公式为grid[i][j] Math.min(grid[i-1][j],grid[i][j-1])grid[i][j];原地修改数组。class Solution { public int minPathSum(int[][] grid) { for(int i 0; i grid.length; i){ for(int j 0; j grid[0].length; j){ if(i 0 j 0){ continue; } if(i 0){ grid[0][j] grid[0][j-1]grid[0][j]; }else if(j 0){ grid[i][0] grid[i-1][0]grid[i][0]; } else grid[i][j] Math.min(grid[i-1][j],grid[i][j-1])grid[i][j]; } } return grid[grid.length-1][grid[0].length-1]; } }5. 最长回文子串 - 力扣LeetCode第一次写错了错误原因为遍历顺序和初始化错误class Solution { public String longestPalindrome(String s) { // dp[i][j] dp[i1][j-1] i,j是否相等 // i, 0-n j i1-n int maxl 0; int maxr 0; int maxlen 1; boolean dp[][] new boolean[s.length()][s.length()]; for(int i 0) for(int i 0; i s.length();i){ for(int j i 1; j s.length();j){ if(s.charAt(i) s.charAt(j) (j-i1||dp[i1][j-1])){ dp[i][j]true; if(j-i1 maxlen){ maxlen j-i1; maxl i; maxr j; } } } } return s.substring(maxl, maxr1); } }公式为dp[i][j] (s.charAt(i) s.charAt(j)) (j - i 1 || dp[i 1][j - 1]);i,j位置依赖的是左下的状态的值需要让左下的值优先计算修正后的代码如下遍历顺序修改需要从行最大列最小的开始计算同时保证JIclass Solution { public String longestPalindrome(String s) { // dp[i][j] dp[i1][j-1] i,j是否相等 // i, 0-n j i1-n int maxl 0; int maxr 0; int maxlen 1; boolean dp[][] new boolean[s.length()][s.length()]; // 保证ji for(int i s.length()-1; i 0;i--){ for(int j i; j s.length();j){ if(s.charAt(i) s.charAt(j) (j-i1||dp[i1][j-1])){ dp[i][j]true; if(j-i1 maxlen){ maxlen j-i1; maxl i; maxr j; } } } } return s.substring(maxl, maxr1); } }1143. 最长公共子序列 - 力扣LeetCode第一次写错考虑从0,i和从0,j的索引位置的字符串组成的最大长度初始化写的不对不如改定义推理含义 两个字符串分别从前i和j个字符组成子序列的最大长度//dp[i][j] dp[i-1][j-1] 1 if (ij)// else max(dp[i-1][j], dp[i][j-1])// 推理顺序依赖左上的数据都是从小到大遍历// 初始化不需要初始化注意点为获取字符的索引位置修改为i-1,j-1保证dp的索引也不越界到0行0列都为0.class Solution { public int longestCommonSubsequence(String text1, String text2) { //推理含义 两个字符串分别从前i和j个字符组成子序列的最大长度 //dp[i][j] dp[i-1][j-1] 1 if (ij) // else max(dp[i-1][j], dp[i][j-1]) // 依赖左上的数据都是从小到大遍历 // 初始化不需要初始化 int dp[][] new int[text1.length()1][text2.length()1]; for(int i 1; i text1.length();i){ for(int j 1; j text2.length();j){ if(text1.charAt(i-1) text2.charAt(j-1)){ dp[i][j] dp[i-1][j-1] 1; }else{ dp[i][j] Math.max(dp[i-1][j], dp[i][j-1]); } } } return dp[text1.length()][text2.length()]; } }72. 编辑距离 - 力扣LeetCode基于最长公共子序列思想dp[i][j]代表把word1的前 i 个字符变成word2的前 j 个字符所需的最少操作数。基于哨兵做边界初始化防止-1越界定义状态转移方程if(word1.charAt(i-1) word2.charAt(j-1)){ dp[i][j] dp[i-1][j-1]; }else{ int temp Math.min(dp[i-1][j], dp[i-1][j-1]); dp[i][j] Math.min(temp, dp[i][j-1])1; }遍历顺序依赖左上、上、左 →i、j都从小到大class Solution { public int minDistance(String word1, String word2) { int m word1.length(); int n word2.length(); // 依赖左边上边左上可以顺序遍历 int dp[][] new int[m1][n1]; // word2为空的时候操作第一个字符串需要删除的次数 for(int i 0; i m;i){ dp[i][0]i; } // word1为空的时候操作第一个字符串需要插入的次数 for(int j 0; j n;j){ dp[0][j]j; } for(int i 1; i m;i){ for(int j 1; j n;j){ // 如果ij相等不用操作考虑前面的就可以 if(word1.charAt(i-1) word2.charAt(j-1)){ dp[i][j] dp[i-1][j-1]; }else{ // 否则考虑i替换为j或者i后面继续插入j位置的字符或者删除i位置字符 int temp Math.min(dp[i-1][j], dp[i-1][j-1]); dp[i][j] Math.min(temp, dp[i][j-1])1; } } } return dp[m][n]; } }总结考虑初始化数组大小状态方程遍历顺序。