Cc36 different subsequences

link ：

Niuke link :
https://www.nowcoder.com/practice/ed2923e49d3d495f8321aa46ade9f873?tpId=46&tqId=29065&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
leetcode link ：
https://leetcode-cn.com/problems/distinct-subsequences/

Description and examples ：

Code ：

Method 1 ：

class Solution {
    
public:
	int numDistinct(string S, string T)
	{
    
		int row = S.size();
		int col = T.size();
		vector<vector<int>> arr(row + 1, vector<int>(col + 1));
		arr[0][0] = 1;
		for (int i = 1; i <= row; ++i)
		{
    
			arr[i][0] = 1;
			for (int j = 1; j <= col; ++j)
			{
    
				if (S[i - 1] == T[j - 1])
					arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
				else
					arr[i][j] = arr[i - 1][j];
			}
		}


		return arr[row][col];
	}
};

Method 1 Analysis ：

The final result is shown in the figure ：

Method 2 ：

class Solution {
    
public:
    int numDistinct(string S, string T)
    {
    
        int row = S.size();
        int col = T.size();
        vector<int> arr(col + 1);
        arr[0] = 1;

        for (int i = 1; i <= row; ++i)
        {
    
            for (int j = col; j > 0; --j)
            {
    
                if (S[i - 1] == T[j - 1])
                    arr[j] = arr[j - 1] + arr[j];
            }
        }
        return arr[col];
    }
};

Method 2 analysis ：

Because we only use one row of data for the two-dimensional array in method 1
When traversing to a point , The value of this point is related to the previous one ：
When the same ： Equal to its own value plus the previous value
When different ： Equal to its own value