LeetCode-115. 不同的子序列

快来打我* 2024-03-24 10:04 1阅读 0赞

#### 目录 ####

*   *  动态规划

题目来源  
[115. 不同的子序列][115.]

### 动态规划 ###

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

dp\[i\]\[j\]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp\[i\]\[j\]。

*  2.确定递推公式

这一类问题，基本是要分析两种情况

> t\[i - 1\] 与 s\[j - 1\]相等  
> t\[i - 1\] 与 s\[j - 1\] 不相等

当t\[i - 1\] 与 s\[j - 1\]相等时，dp\[i\]\[j\]可以有两部分组成。  
一部分是用t\[i - 1\]来匹配，那么个数为dp\[i - 1\]\[j - 1\]。即不需要考虑当前s子串和t子串的最后一位字母，所以只需要 dp\[i-1\]\[j-1\]。  
一部分是不用s\[j - 1\]来匹配，个数为dp\[i\]\[j-1\]。

**例如：** s：bagg 和 t：bag ，s\[3\] 和 t\[2\]是相同的，但是字符串s也可以不用s\[3\]来匹配，即用s\[0\]s\[1\]s\[2\]组成的bag。  
当然也可以用s\[3\]来匹配，即：s\[0\]s\[1\]s\[3\]组成的bag。  
所以当t\[i - 1\] 与 s\[j - 1\]相等时，dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\] + dp\[i \]\[j-1\];

当t\[i - 1\] 与 s\[j - 1\]不相等时，dp\[i\]\[j\]只有一部分组成，不用s\[j - 1\]来匹配（就是模拟在s中删除这个元素），即：dp\[i\]\[j-1\]  
所以递推公式为：dp\[i\]\[j\] = dp\[i\]\[j-1\];

为什么只考虑 不用s\[j - 1\]来匹配 这种情况， 不考虑 不用t\[i - 1\]来匹配 的情况呢。  
我们求的是 s 中有多少个 t，而不是 求t中有多少个s，所以只考虑 s中删除元素的情况，即 不用t\[i - 1\]来匹配 的情况。

*  3.dp数组如何初始化

从递推公式dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\] + dp\[i\]\[j-1\]; 和 dp\[i\]\[j\] = dp\[i\]\[j-1\]; 中可以看出dp\[i\]\[j\] 是从左方和左上方推导而来，那么 dp\[i\]\[0\] 和dp\[0\]\[j\]是一定要初始化的。

dp\[0\]\[j\] 表示：以j-1为结尾的s可以随便删除元素，出现空字符串的个数。  
![在这里插入图片描述][c789c3aacd0c442f8a6a9651ea65a7cc.png]  
那么dp\[i\]\[0\]一定都是0，s如论如何也变成不了t。

*  4.确定遍历顺序

从递推公式dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\] + dp\[i \]\[j-1\]; 和 dp\[i\]\[j\] = dp\[i \]\[j-1\]; 中可以看出dp\[i\]\[j\]都是根据左上方和正上方推出来的。  
所以遍历的时候一定是从上到下，从左到右，这样保证dp\[i\]\[j\]可以根据之前计算出来的数值进行计算。

*  5.举例推导dp数组

S = “babgbag”, T = “bag” ，推导dp数组状态如下：  
![在这里插入图片描述][c216a063ec734dc58d463f59b0c4cc05.png]  
代码实现

class Solution {
        
        public int numDistinct(String s, String t) {
        
            int[][] dp = new int[t.length()+1][s.length()+1];
            for(int i = 0;i<=s.length();i++){
        
                dp[0][i] = 1;
            }
            for(int i=1;i<=t.length();i++){
        
                for(int j= 1;j<=s.length();j++){
        
                    if(t.charAt(i-1) == s.charAt(j-1)){
        
                        dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
                    }else{
        
                        dp[i][j] = dp[i][j-1];
                    }
                }
            }
            return dp[t.length()][s.length()];
    
        }
    }

![在这里插入图片描述][1097e0631a864620b7920fb5152bd99c.png]

[115.]: https://leetcode.cn/problems/distinct-subsequences/
[c789c3aacd0c442f8a6a9651ea65a7cc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/93572796c1f14553badd2ccf98e78b87.png
[c216a063ec734dc58d463f59b0c4cc05.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/626e30ae2c784ac0be2bd5443875e4cf.png
[1097e0631a864620b7920fb5152bd99c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/7816a4066af24fa88886ea705892758d.png