【动态规划】二维数组的dp问题 不同的子序列_最优值二维dp表

题目链接：https://leetcode.cn/problems/21dk04/

一.关于字符串类子序列问题的注意事项

        1. 这类问题在填表时由于状态方程的限制，需要[i - 1]或[i - 1][j - 1]时的状态，此时在数组前一个或者前一列前一行中开辟额外空间，辅助填表。此时在填表时时刻注意下标的对应关系，还有填表后的数值是否正确。

        2. 在开辟辅助空间时，可以在题目原字符串前 + " "，来方便下标对齐，此时在填表中dp表中的位置就与原字符串中的位置对应。

        3. 在初始化时要考虑空串的情况，在部分题目里允许出现" "空串。

二.题目介绍

三.题目分析

        此题要求在字符串s的子序列中计算字符串t出现的次数，我们继续用"子序列问题"的思想在一段区间中分析状态，然后以某一位置为结尾分析状态方程。用二维数组存放字符串s以 i为结尾的区间的状态和字符串t以 j为结尾的区间的状态，dp[ i ][ j ]表示字符串s以 i为结尾的子序列中有多少个字符串t以 j结尾的子序列，注意题目要求"在字符串s的子序列中计算字符串t出现的次数"，看上去只要求算出有多少 t字符串出现就可以，但是对t 子序列的统计才能辅助得到最终结果。

四.状态分析

五.完整代码

 // 很需要理解的题。
    int numDistinct(string s, string t) 
    {
        int m = s.size(), n = t.size();
        vector<vector<double>> dp(m+1, vector<double>(n+1));
        for(int i = 0; i < m+1; i++)
        {
            dp[i][0] = 1;
        }
    
        for(int i = 1; i < m+1; i++)
        {
            for(int j = 1; j < n+1; j++)
            {
                double tmp1 = 0, tmp2 = 0;
                tmp2 = dp[i-1][j];
                if(s[i-1] == t[j-1])
                    tmp1 = dp[i-1][j-1];
 
                dp[i][j] = tmp1 + tmp2;
            }
           
        }
 
        return (int)dp[m][n];
    }