https://leetcode-cn.com/problems/distinct-subsequences/

  • 困难
  • 中等
  • 简单

image.png

思路

动态规划

  1. class Solution {
  2. public:
  3.     int numDistinct(string s, string t) {
  4.         vector<vector<long>> dp(t.length() + 1, vector<long>(s.length() + 1));
  5.         for (int i = 0; i < s.length(); i++) {
  6.             dp[0][i] = 1;
  7.         }
  8.         // dp[i][j]表示t前i个字符可以由s的前j个组成的最多个数
  9.         for (int i = 1; i <= t.length(); i++) {
  10.             for (int j = 1; j <= s.length(); j++) {
  11.                 if (s[j-1] == t[i-1]) {
  12.                     dp[i][j] = dp[i][j-1] + dp[i-1][j-1];
  13.                 } else {
  14.                     dp[i][j] = dp[i][j-1];
  15.                 }
  16.             }
  17.         }
  18.         return dp[t.length()][s.length()];
  19.     }
  20. };