多维动态规划
不同路径
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/
核心思路
- 双重循环遍历：
- 外层循环遍历字符串中的每个字符，作为回文中心的可能起点。
- 内层循环遍历两种情况：奇数长度回文和偶数长度回文。
j=0代表奇数长度回文（中心是一个字符），j=1代表偶数长度回文（中心是两个字符之间的空隙）。
- 双指针扩展：
- 对于每个回文中心（或中心空隙），使用两个指针
left和right分别向左和向右扩展，检查字符是否相等。 - 如果相等，继续扩展；如果不相等，停止扩展。
- 对于每个回文中心（或中心空隙），使用两个指针
- 调整指针位置：
- left多减了一次，right多加了一次。
- 更新最长回文信息：
示例代码
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/
核心思路
-
定义状态:
使用一个二维数组f，其中f[i][j]表示 text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列的长度。 -
状态转移方程:
如果 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];}
}
