Distinct Subsequences [Leetcode]

Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.

Solution: this is a DP problem; our objective is to count the number of appearance of T in S where some char can be inserted into T.
Transitive function is: dp(i,j) = dp(i-1,j) + (S[i]==S[j]?dp(i-1,j-1):0), where dp(i,j) means the number of distinct subsequences of T[0,..., j] in S[0,...,i].

class Solution {
public:
    int numDistinct(string S, string T) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int s = S.size();
        int t = T.size();
        if(s==0 || t==0 || s<t) return 0;
        vector<vector<int>> cache(s, vector<int>(t, 0));
        cache[0][0]= (S[0]==T[0]?1:0);
        for(int i=1; i<s; ++i){
            for(int j=0; j<=min(i, t-1); ++j){
                if(j==0)
                    cache[i][j] = cache[i-1][j]+(S[i]==T[j]?1:0);
                else
                    cache[i][j] = cache[i-1][j]+(S[i]==T[j]?cache[i-1][j-1]:0);
            }
        }
        return cache[s-1][t-1];

    }
};

It is to be noted that when we do i-th iteration, we only need the result in (i-1)-th iteration. So here we only need one-dimensional array of size t, where t is the length of T.  Consider the i-th iteration: at the beginning of the iteration: cache[j] is the number of distinct subsequences of T[0,..., j] in S[0,...,i-1]; while it is updated to the number of distinct subsequences of T[0,..., j] in S[0,...,i] in the end of i-th iteration.

class Solution {
public:
    int numDistinct(string S, string T) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int s = S.size();
        int t = T.size();
        if(s==0 || t==0 || s<t) return 0;

        vector<int> cache(t, 0);
        for(int i=0; i<s; ++i)
            for(int j=min(i, t-1); j>=0; j--){
                if(S[i]==T[j])
                    cache[j] += (j==0?1:cache[j-1]);
            }
        return cache[t-1];
    }
};