給定一個字符串 s 和一個字符串 t ，計算在 s 的子序列中 t 出現的個數。

字符串的一個 子序列 是指，通過刪除一些（也可以不刪除）字符且不干擾剩余字符相對位置所組成的新字符串。（例如，“ACE” 是 “ABCDE” 的一個子序列，而 “AEC” 不是）

題目數據保證答案符合 32 位帶符號整數范圍。

示例 1：

輸入：s = “rabbbit”, t = “rabbit”
輸出：3
解釋：
如下圖所示, 有 3 種可以從 s 中得到 “rabbit” 的方案。
(上箭頭符號 ^ 表示選取的字母)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

解題思路

狀態轉移方程
dp[i][m1]= s.charAt(i)==t.charAt(m1)?dp[i+1][m1+1]+dp[i+1][m1]:dp[i+1][m1];
dp[i][m1]代表s[i…]和t[m1…]情況下，子序列的個數
初始化 當m1=m時代表字符串t為空串，任何s的子串都能匹配 ，所以dp[i][m]=1;

代碼

public int numDistinct(String s, String t) {int n=s.length(),m=t.length();if(n<m) return 0;int[][] dp = new int[n+1][m+1];for (int i = n-1; i >= 0; i--) dp[i][m]=1;for (int i = n-1; i >=0; i--) for (int m1 = m-1; m1 >=0; m1--) dp[i][m1]= s.charAt(i)==t.charAt(m1)?dp[i+1][m1+1]+dp[i+1][m1]:dp[i+1][m1];return dp[0][0];}

總結

以上是生活随笔為你收集整理的leetcode 115. 不同的子序列（dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。