hot100之多维动态规划

我是比较爱用自底向上的自底向上方法不会计算多余情况， 也不用memo存储

不同路径（062）

class Solution {
 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];
 }
}

• 分析

对0行0列初始化，后进行合流

最小路径和（064）

class Solution {
 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 = 1; i < m; i++){
 for (int j = 1; j < n; j++){
 dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
 }
 }
 return dp[m-1][n-1];
 }
}

• 分析

同样是初始化， 再合流

根据dp数组的依赖关系， 可以进行空间优化

最长回文子串（005）

class Solution {
 public String longestPalindrome(String s) {
 String res = " ";
 for (int i = 0; i < s.length(); i++){
 String str1 = longestSubPalindrome(i, i, s);
 String str2 = longestSubPalindrome(i, i+1, s);
 res = res.length() > str1.length() ? res : str1;
 res = res.length() > str2.length() ? res : str2;
 }
 return res;
 }
 private String longestSubPalindrome(int lef, int rig, String s){
 while (0<=lef && rig < s.length() && s.charAt(lef) == s.charAt(rig)){
 lef--;
 rig++;
 }
 return s.substring(lef+1, rig);
 }
}

• 分析

想到扩散是比较自然的，时间复杂度也不高

最长公共子序列（1143）

class Solution {
 public int longestCommonSubsequence(String text1, String text2) {
 char[] charArray1 = text1.toCharArray();
 char[] charArray2 = text2.toCharArray();
 int m = charArray1.length;
 int n = charArray2.length;
 int[][] dp = new int[m+1][n+1];
 for(int i = 1; i <= m; i++){
 for (int j = 1; j <= n; j++){
 if (charArray1[i-1] == charArray2[j-1]){
 dp[i][j] = dp[i-1][j-1] + 1;
 }
 else dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
 
 }
 }
 return dp[m][n];
 }
}

• 分析

可以看作有两个指针， 匹配的话两个指针一起右移， 不匹配移动其中一个指针找到新的匹配

编辑距离（072）

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

• 分析

跟上题差不多，不匹配时多了一个情况变为<移动A指针><移动B指针><移动双指针>