多维动态规划

2 天前	#72 编辑距离	中等	3 次
2 天前	#1143 最长公共子序列	中等	2 次
2 天前	#5 最长回文子串	中等	16 次
2 天前	#64 最小路径和	中等	1 次
2 天前	#62 不同路径	中等	2 次

备注：

1、不同路径最小路径和直接过无非就是 i-1 j 跟 i j-1的比较

2、最长公共子序列是从1开始for循环然后也是 i-1 j 跟 i j-1 字符相等是 i-1 j-1

3、编辑距离很最长公共子序列一样但是不同点是在于if条件的判断

 								if (c == d) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }							

								if(c == d){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j]  = Math.min(Math.min(dp[i-1][j-1], dp[i][j-1]), dp[i-1][j])+1;
                }

1
2
3
4
5
6
7
8
9
10
11

4、最长回文子串：可不用动态规划

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if(len == 1){
            return s;
        }
        int max = 0;
        String str = "";
        for(int i = 0; i< len; i++){
            for(int j = i; j< len; j++){
                if(isVaild(s, i, j)){
                    if(j-i+1 > max){
                        max = j-i+1;
                        str = s.substring(i, j+1);
                    }
                    
                }
            }
        }
        return str;

    }


    public boolean isVaild(String s, int l, int r){
        if(l> r){
            return false;
        }
        while(l<= r){
            if(s.charAt(l) != s.charAt(r)){
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

回文子序列：也是动态规划

public class Solution {
    public int longestPalindromeSubseq(String s) {
        int len = s.length();
        int[][] dp = new int[len + 1][len + 1];
        for (int i = len - 1; i >= 0; i--) { // 从后往前遍历 保证情况不漏
            dp[i][i] = 1; // 初始化
            for (int j = i + 1; j < len; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], Math.max(dp[i][j], dp[i][j - 1]));
                }
            }
        }
        return dp[0][len - 1];
    }
}
思路：
  1、基本 来回 就是 两层for  开始先初始化值 ，之后就是字符串的比较 然后不同情况 对应不同情况的表达式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 不同路径

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][j-1] + dp[i-1][j];
           }
       }
        return dp[m-1][n-1];
    }
}
思路：
  1、先填充1（边上）
  2、然后m n 分别遍历  
  3、 dp[i][j] = dp[i][j-1] + dp[i-1][j];  经典表达式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 最小路径和

class Solution {
    public int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        //填充
        dp[0][0] = grid[0][0];
        for(int i = 1; i< grid.length; i++){
            dp[i][0] = dp[i-1][0]+ grid[i][0];
        }
        for(int j = 1; j< grid[0].length; j++){
            dp[0][j] = dp[0][j-1]+ grid[0][j];
        }
        //缓存值
        for(int i = 1; i< grid.length; i++  ){
            for(int j = 1; j< grid[0].length; j++){
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1])+ grid[i][j];
            }
        }
        return dp[grid.length-1][grid[0].length-1];


    }
}

思路：
  1、定义  先对 00位置填充
  2、然后对两边填充
  3、之后缓存值   dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1])+ grid[i][j];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# 最长回文子串

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        String res = "";
        boolean[][] dp = new boolean[n][n];
        for(int i = n-1; i >= 0; i--){
            for(int j = i; j < n; j++){
                dp[i][j] = s.charAt(i) == s.charAt(j) && (j-i < 2 || dp[i+1][j-1]);
                if(dp[i][j] && j-i+1 > res.length()){
                    res = s.substring(i,j+1);
                }
            }
        }
        return res;
    }
}
思路：
  1、boolean[][] 的 dp
  2、for循环 以及这一段 dp[i][j] = s.charAt(i) == s.charAt(j) && (j-i < 2 || dp[i+1][j-1]);
                if(dp[i][j] && j-i+1 > res.length()){
                    res = s.substring(i,j+1);
                } 直接背吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 最长公共子序列

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        int[][] dp = new int[len1+1][len2+1];
        for(int i =1; i<= len1;i++){
            char c = text1.charAt(i-1);
            for(int j= 1; j<= len2; j++){
                char d = text2.charAt(j-1);
                if(c == d){
                    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[len1][len2];
    }   
}
思路：
  1、

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 编辑距离

class Solution {
    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 = 1; 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-1], dp[i][j-1]), dp[i-1][j])+1;
                }
            }
        }
        return dp[m][n];
    }
}
思路：
  1、

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

编辑

上次更新: 2024/03/26, 9:03:00

← 动态规划技巧 →