多维动态规划 力扣hot100热门面试算法题 面试基础 核心思路 背题

多维动态规划

不同路径

https://leetcode.cn/problems/unique-paths/

核心思路

比较简单

f[i][j] = f[i - 1][j] + f[i][j - 1] ;

示例代码

class Solution {public int uniquePaths(int n, int m) {int[][] f = new int[n][m];for (int i = 0; i < n; i++)f[i][0] = 1;for (int j = 0; j < m; j++)f[0][j] = 1;if (n + m >= 4) {for (int i = 1; i < n; i++) {for (int j = 1; j < m; j++) {f[i][j] += f[i - 1][j];f[i][j] += f[i][j - 1];}}}return f[n - 1][m - 1];}
}

最小路径和

https://leetcode.cn/problems/minimum-path-sum/

核心思路

比较简单

f[i][j]为到达（i，j）处 的最短路径和

示例代码

class Solution {public int minPathSum(int[][] f) {int n = f.length;int m = f[0].length;for (int i = 1; i < n; i++)f[i][0] += f[i-1][0];for (int j = 1; j < m; j++)f[0][j] += f[0][j-1];if(n+m>=4){for (int i = 1; i < n; i++) {for (int j = 1; j < m; j++) {f[i][j] += Math.min(f[i - 1][j],f[i][j - 1]);}}}return f[n - 1][m - 1];}
}

最长回文子串

https://leetcode.cn/problems/longest-palindromic-substring/

核心思路

1. 双重循环遍历：
   • 外层循环遍历字符串中的每个字符，作为回文中心的可能起点。
   • 内层循环遍历两种情况：奇数长度回文和偶数长度回文。j=0代表奇数长度回文（中心是一个字符），j=1代表偶数长度回文（中心是两个字符之间的空隙）。
2. 双指针扩展：
   • 对于每个回文中心（或中心空隙），使用两个指针left和right分别向左和向右扩展，检查字符是否相等。
   • 如果相等，继续扩展；如果不相等，停止扩展。
3. 调整指针位置：
   • left多减了一次，right多加了一次。
4. 更新最长回文信息：

示例代码

class Solution {public String longestPalindrome(String s) {char[] ch = s.toCharArray();int n = ch.length;int maxStart = 0;int maxLength = 0;for(int i = 0; i < n; i++){for(int j =0; j < 2; j++){int left = i;int right = i+j;while(left >= 0 && right < n && ch[left] == ch[right]){left--;right++;}left++;right--;if(maxLength<right-left+1){maxLength = right - left + 1;maxStart = left;}}}return s.substring(maxStart,maxStart+maxLength);}
}

最长公共子序列

https://leetcode.cn/problems/longest-common-subsequence/

核心思路

1. 定义状态:
   使用一个二维数组 f，其中 f[i][j] 表示 text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列的长度。

2. 状态转移方程:
   如果 text1[i-1] 与 text2[j-1] 相等（注意索引偏移），那么可以通过 f[i-1][j-1] 加 1 来更新 f[i][j]： [ f[i][j] = f[i-1][j-1] + 1 ]
   如果不相等，则最长公共子序列的长度为从 text1 的前 i 个字符与 text2 的前 j-1 个字符或 text1 的前 i-1 个字符与 text2 的前 j 个字符中选择较大的：

   ​ [ f[i][j] = max(f[i-1][j], f[i][j-1]) ]

示例代码

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

class Solution {public int longestCommonSubsequence(String text1, String text2){int n=text1.length();int m=text2.length();char[] t=text2.toCharArray();int [] f=new int[m+1];for(char x:text1.toCharArray()){int pre=0;for(int j=0;j<m;j++){int temp=f[j+1];f[j+1]= x==t[j] ? pre+1 : Math.max(f[j],f[j+1]);pre=temp;}}return f[m];}
}

编辑距离

https://leetcode.cn/problems/edit-distance/

核心思路

f[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小操作次数。

示例代码

class Solution {public int minDistance(String word1, String word2) {int n = word1.length();int m = word2.length();int[][] f = new int[n + 1][m + 1];for (int i = 0; i <= m; i++)f[0][i] = i;for (int i = 0; i <= n; i++)f[i][0] = i;for (int i = 0; i < n; i++)for (int j = 0; j < m; j++) {//相等就不动if (word1.charAt(i) == (word2.charAt(j)))f[i + 1][j + 1] = f[i][j];else {//插入与替换f[i + 1][j + 1] = Math.min(Math.min(f[i + 1][j], f[i][j + 1]), f[i][j]) + 1;}}return f[n][m];}
}