My C++ Simple DP Solution


  • 0
    N
    class Solution {
    public:
    	int numDistinct(string s, string t) {
    		int slen = s.size(), tlen = t.size();
    		if (slen < 1 || tlen < 1) return 0;
    		vector<vector<int>> dp(slen);
    		for (int i = 0; i < slen; i++) {
    			dp[i].resize(tlen + 1);
    			dp[i][tlen] = 1;
    		}
    		dp[slen - 1][tlen - 1] = s[slen - 1] == t[tlen - 1];
    		for (int i = slen - 2; i >= 0; i--)
    			for (int j = 0; j < tlen; j++)
    				dp[i][j] = dp[i + 1][j] + dp[i + 1][j + 1] * (s[i] == t[j]);
    		return dp[0][0];
    	}
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.