算法训练营（day56）

动态规划理论基础

动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

举个例子：有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

动态规划中 dp[j] 是由 dp[j-weight[i]] 推导出来的，然后取 max(dp[j], dp[j - weight[i]] + value[i])。

动态规划的解题步骤

  1. 确定 dp 数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp 数组如何初始化
  4. 确定遍历顺序
  5. 举例推导 dp 数组

647. 回文子串

题目链接：https://leetcode.cn/problems/palindromic-substrings/description/

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

解题思路

解题过程：动态规划

按照动规五部曲来分析：

  1. 确定dp数组（dp table）以及下标的含义

​ dp[j]表示容量为j的背包，最多可以背最大重量为dp[j]

​ 本题的 dp[i][j]：判断是否是回文

  1. 确定递推公式
  • s[i] 与 s[j] 相同，则有三种情况
    • i = j，单个元素自然是回文
    • |j - i| = 1，相邻的两个元素组成回文
    • |j - i| > 1的情况，如果此时的 s[i] 与 s[j] 已经相同了，要考虑 s[i + 1] 与 s[j - 1] 是否相同
img
  • s[i] 与 s[j] 不相同，则 dp[i][j] = false

所以得到的递推公式就是：

1
2
3
4
5
6
7
8
9
if(s.charAt(i) == s.charAt(j)){
    if(j - i < 3){
        dp[i][j] = true;
    }else {
        dp[i][j] = dp[i + 1][j - 1];
    }
}else{
    dp[i][j] = false;
}

  1. dp数组的初始化

    dp 的初始化为 false

1
boolean[][] dp = new boolean[len][len];
  1. 确定遍历顺序

​ 简单理解，j 要从右往左遍历，i 要从左往右遍历，当 i = j 时，说明整个字符串遍历结束

​ 用矩阵解释：

647.回文子串

​ 要从下到上，从左到右遍历，这样保证 dp[i + 1][j - 1] 都是经过计算的

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int j = 0; j < len; j++){
    for(int i = 0; i <= j; i++){
        if(s.charAt(i) == s.charAt(j)){
            if(j - i < 3){
                dp[i][j] = true;
            }else {
                dp[i][j] = dp[i + 1][j - 1];
            }
        }else{
            dp[i][j] = false;
        }
    }
}
  1. 推导dp数组

详细代码

动态规划：

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
class Solution {
    public int countSubstrings(String s) {
        int len = s.length();
        int res = 0;
        if(s == null || len == 0){
            return 0;
        }

        boolean[][] dp = new boolean[len][len];
        for(int j = 0; j < len; j++){
            for(int i = 0; i <= j; i++){
                if(s.charAt(i) == s.charAt(j)){
                    if(j - i < 3){
                        dp[i][j] = true;
                    }else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }else{
                    dp[i][j] = false;
                }
            }
        }
        for(int i = 0; i < len; i++){
            for(int j = 0; j < len; j++){
                if(dp[i][j]){
                    res++;
                }
            }
        }
        return res;
    }
}

中心扩散：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int countSubstrings(String s) {
        int len = s.length();
        int res = 0;
        
        for(int i = 0; i < 2 * len -1; i++){
            int left = i / 2;
            int right = left + i % 2;;
            while(left >= 0 && right < len && s.charAt(left) == s.charAt(right)){
                res++;
                left--;
                right++;
            }
        }
        return res;
    }
}

516. 最长回文子序列

题目链接：https://leetcode.cn/problems/longest-palindromic-subsequence/

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

解题思路

解题过程：动态规划

按照动规五部曲来分析：

  1. 确定dp数组（dp table）以及下标的含义

​ dp[j]表示容量为j的背包，最多可以背最大重量为dp[j]

​ 本题的 dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度

回文子串是要连续的，回文子序列可不是连续的

  1. 确定递推公式

​ 关键逻辑就是看 s[i] 与 s[j] 是否相同

  • s[i] 与 s[j] 相同，则dp[i][j] = dp[i + 1][j - 1] + 2
516.最长回文子序列
  • s[i] 与 s[j] 不相同，则有三种情况：
    • 单加一个 s[i]，则 dp[i][j] = dp[i][j - 1]
    • 单加一个 s[j] ，则 dp[i][j] = dp[i + 1][j]
    • 都没得加 ，则 dp[i][j] = dp[i + 1][j - 1]
516.最长回文子序列1

​ 最后得到递推公式是：

1
2
3
4
5
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]));
}

  1. dp数组的初始化

    首先需要手动初始化 i = j时的dp：

1
2
3
4
5
int[][] dp = new int[len + 1][len + 1];    
for (int i = len - 1; i >= 0; i--){
    dp[i][i] = 1;
    ...
}

​ 其他情况的dp初始化为0即可

  1. 确定遍历顺序

​ 从递推公式可以看出，dp[i][j] 依赖于dp[i + 1][j - 1] 、 dp[i][j - 1] 和 dp[i + 1][j]，所以遍历i的时候一定要从下到上遍历，这样才能保证下一行的数据是经过计算的，j 可以正常的从左到右。

img 
1
2
3
4
5
6
7
8
9
10
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]));
        }
    }
}
  1. 推导dp数组

详细代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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];
    }
}