算法训练营（day54）

动态规划理论基础

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

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

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

动态规划的解题步骤

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

392. 判断子序列

题目链接：https://leetcode.cn/problems/is-subsequence/description/

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

解题思路

解题过程：动态规划

按照动规五部曲来分析：

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

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

本题的 dp[i][j]：以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度

确定递推公式

s[i - 1] 与 t[j - 1] 相同，则dp[i][j] = dp[i - 1][j - 1] + 1
s[i - 1]与 t[j - 1] 不相同，则 dp[i][j] = dp[i][j - 1])

所以递推公式是：

if(s.charAt(i - 1) == t.charAt(j - 1)){
    dp[i][j] = dp[i - 1][j - 1] + 1;
}else {
    dp[i][j] = dp[i][j - 1];
}

dp数组的初始化

因为 dp[0][0] 的值会随着遍历被覆盖，所以直接初始化为0即可。

1	int[][] dp = new int[text1.length() + 1][text2.length() + 1];

确定遍历顺序

根据递推公式可以得出，dp[i][j] 依赖于dp[i - 1][j - 1] 和 dp[i][j - 1] ，是从前到后，从左往右遍历的一个矩阵

for(int i = 1; i < m + 1; i++){
    for(int j = 1; j < n + 1; j++){
        if(s.charAt(i - 1) == t.charAt(j - 1)){
            dp[i][j] = dp[i - 1][j - 1] + 1;
        }else {
            dp[i][j] = dp[i][j - 1];
        }
    }
}

推导dp数组

详细代码

class Solution {
    public boolean isSubsequence(String s, String t) {
        int m = s.length();
        int n = t.length();
        int[][] dp = new int[m + 1][n + 1];

        for(int i = 1; i < m + 1; i++){
            for(int j = 1; j < n + 1; j++){
                if(s.charAt(i - 1) == t.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        if(dp[m][n] == m){
            return true;
        }
        return false;
    }
}

115. 不同的子序列

题目链接：https://leetcode.cn/problems/distinct-subsequences/description/

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。