C++ 解法, 执行用时: 5ms, 内存消耗: 404KB, 提交时间: 2022-07-21

class Solution {
  public:
    int countSubseq(string s, string t) {
        int H = s.size();
        int L = t.size();

        vector<unsigned> v(L + 1);
        v[0] = 1;

        for (int i = 0; i < H; ++i) {
            for (int j = L - 1; j >= 0; --j) {
                v[j + 1] += s[i] == t[j] ? v[j] : 0;
            }
        }

        return v[L];
    }
};

C++ 解法, 执行用时: 5ms, 内存消耗: 404KB, 提交时间: 2022-07-07

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param t string字符串 
     * @return int整型
     */
    int countSubseq(string s, string t) {
        /*int n = s.size(), m = t.size();
        vector<vector<int> > dp(n + 1, vector<int>(m + 1));
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                if (j >= 1 && s[i - 1] == t[j - 1]) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
                dp[i][j] += dp[i - 1][j];
            }
        }
        return dp[n][m];*/
        int m = s.size();
        int n = t.size();
        vector<unsigned> f(n + 1);
 
        f[0] = 1;
         
        for (int i = 0; i < m; ++i) {
            for (int j = n - 1; j >= 0; --j) {
                f[j + 1] += s[i] == t[j] ? f[j] : 0;
            }
        }
         
        return f[n];
    }
};

C++ 解法, 执行用时: 5ms, 内存消耗: 416KB, 提交时间: 2022-06-30

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param t string字符串 
     * @return int整型
     */
    int countSubseq(string s, string t) {
        // write code here
        int m = s.size();
        int n = t.size();
        vector<unsigned> f(n + 1);

        f[0] = 1;
        
        for (int i = 0; i < m; ++i) {
            for (int j = n - 1; j >= 0; --j) {
                f[j + 1] += s[i] == t[j] ? f[j] : 0;
            }
        }
        
        return f[n];
    }
};

C++ 解法, 执行用时: 5ms, 内存消耗: 428KB, 提交时间: 2022-08-06

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param t string字符串 
     * @return int整型
     */
    int countSubseq(string s, string t) {
        // write code here
        int H=s.size();
        int L=t.size();
        vector<unsigned> v(L+1);
        v[0]=1;
        for(int i=0;i<H;++i)
        {
            for(int j=L-1;j>=0;--j)
            {
                v[j+1]+=s[i]==t[j]?v[j]:0;
            }
        }
        return v[L];
    }
};

C++ 解法, 执行用时: 6ms, 内存消耗: 408KB, 提交时间: 2022-04-04

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @param t string字符串
     * @return int整型
     */
    int countSubseq(string const& s, string const& t);
};

int Solution::countSubseq(string const& s, string const& t) {
    // write code here
    const size_t sn = s.length(), tn = t.length();
    if (sn <= tn) return s == t ? 1 : 0;
    vector<int> dpPrev(sn+1, 1), dp(sn+1, 0);
    for (size_t i = 1; i <= tn; i++) {
        dp[i-1] = 0;
        for (size_t j = i; j <= sn; j++) {
            dp[j] = dp[j-1] + (s[j-1] == t[i-1] ? dpPrev[j-1] : 0);
        }
        dp.swap(dpPrev);
    }
    return dpPrev.back();
}