力扣100题——二维动态规划

不同路径

题目

62. 不同路径 - 力扣（LeetCode）

思路

• 使用dp数组代表到达当前位置的路径最大条数
• 状态转移方程即为 dp[i][j]=dp[i-1][j]+dp[i][j+1]

代码

 public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];for(int i=0;i<m;i++){dp[i][0]=1;}for(int j=0;j<n;j++){dp[0][j]=1;}for(int i=1;i<m;i++){for(int j=1;j<n;j++){dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m-1][n-1];}

最小路径和

题目

64. 最小路径和 - 力扣（LeetCode）

思路

思路和上一题差不多，只不过状态转移方程略有不同

• 使用dp数组代表到达当前位置的最小路径和
• 状态转移方程即为 dp[i][j]=Math.min(dp[i-1][j],dp[i][j+1])+grid[i][j]

代码

public int minPathSum(int[][] grid) {int m = grid.length;int n = grid[0].length;int[][] dp = new int[m][n];dp[0][0]=grid[0][0];for(int i=1;i<m;i++){dp[i][0] = dp[i-1][0]+grid[i][0];}for(int j=1;j<n;j++){dp[0][j] = dp[0][j-1]+grid[0][j];}for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(i==0&&j==0){continue;}int a = i-1>=0?dp[i-1][j]:Integer.MAX_VALUE;int b = j-1>=0?dp[i][j-1]:Integer.MAX_VALUE;dp[i][j] = Math.min(a,b)+grid[i][j];}}return dp[m-1][n-1];}

最长回文子串

题目

5. 最长回文子串 - 力扣（LeetCode）

思路

• 定义状态：使用一个二维布尔数组 dp，其中 dp[i][j] 表示子串 s[i:j+1] 是否是回文串。
• 初始化：
  • 单个字符的子串始终是回文，因此 dp[i][i] = true。
  • 两个字符的子串 s[i:i+1] 如果两个字符相同，则 dp[i][i+1] = true。
• 状态转移：
  • 对于长度大于 2 的子串 s[i:j+1]，如果 s[i] == s[j] 且 dp[i+1][j-1] 是回文，则 dp[i][j] 也为回文。
• 结果维护：遍历所有 dp[i][j]，找到最长的回文子串，并记录其起始位置和长度。

代码

 public String longestPalindrome(String s) {int n = s.length();boolean[][] dp = new boolean[n][n];for(int i=0;i<n;i++){dp[i][i]=true;}int start = 0;int maxLen = 1;for(int i=0;i<n-1;i++){if(s.charAt(i)==s.charAt(i+1)){dp[i][i+1]=true;start=i;maxLen=2;}}for(int length=3;length<=s.length();length++){for(int i=0;i<s.length()-length+1;i++){int j = i+length-1;if(s.charAt(i)==s.charAt(j)&&dp[i+1][j-1]){dp[i][j]=true;start=i;maxLen=length;}}}return s.substring(start,start+maxLen);}

最长公共子序列

题目

1143. 最长公共子序列 - 力扣（LeetCode）

思路

用dp[i][j]代表text1前i个字符和text2前j个字符的最长公共子序列长度

状态转移方程：

• 当test1[i-1]==test2[j-1]时 dp[i][j]=dp[i-1][j-1]+1
• 反之则 dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])

代码

public int longestCommonSubsequence(String text1, String text2) {int m = text1.length();int n = text2.length();int[][] dp = new int[m+1][n+1];for(int i=0;i<=m;i++){for(int j=0;j<=n;j++){if(i==0||j==0){dp[i][j]=0;}}}for(int i=1;i<=m;i++){for(int j=1;j<=n;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[m][n];}

编辑距离

题目

72. 编辑距离 - 力扣（LeetCode）

思路

• dp[i][j]代表word1前i个字符和word2前j个字符的最小编辑长度
• 首先是初始化
  • 当j=0，dp[i][0]即为i的长度，也就是删除i个字符
  • 当i=0，dp[0][j]即为j的长度，也即是插入j个字符
• 状态转移方程
  • 当 word1.charAt(i-1)==word2.charAt(j-1) 时，编辑长度不变 dp[i][j]=dp[i-1][j-1]
  • 反之 dp[i][j]=dp[i-1][j],dp[i][j-1],dp[i-1][j-1]的最小值加1。其中dp[i-1][j]代表删除一个字符，dp[i][j-1]代表新增一个字符，dp[i-1][j-1]代表替换一个元素

代码

public int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();int[][] dp = new int[m+1][n+1];for(int i=0;i<=m;i++){dp[i][0]=i;}for(int j=1;j<=n;j++){dp[0][j]=j;}for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(word1.charAt(i-1)==word2.charAt(j-1)){dp[i][j]=dp[i-1][j-1];}else{dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;}}}return dp[m][n];}