Leetcode Distinct Subsequences 动态规划法活用总结

Distinct Subsequences

Given a stringSand a stringT, count the number of distinct subsequences ofTinS.

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"

Return3.

动态规划法活用总结：
1 二维表：很多问题都可以转化为二维表
2 三维表：比较难理解，时间效率一般是O(n*n*n)
3 二维表变一维表：一般是简化二维表，不需要保存整个表
4 一维表变常量：一般是由一维表简化而来，一维表也不需要保存，只保存当前结果和当前结果需要用的变量就可以
5 逆向填表：根据表进一步抽象简化出来，可以让程序更加简洁，当然也更加更加难理解。

设计动态规划法算法，应该循序渐进，先设计二维表或三维表，然后再简化，进一步优化，再简化，不要一步就写最简化的程序。

熟练之后，可以直接设计表，根据表特征，翻译为程序。

熟练递归回溯法有助于动态规划法的深入理解。

//最好理解的二维动态规划法，一次性ac。
	int numDistinct2(string S, string T) 
	{
		vector<vector<int> > ta(T.size()+1, vector<int>(S.size()+1));
		for (int i = 0; i <= S.size(); i++)
		{
			ta[0][i] = 1;
		}
		for (int i = 1; i <= T.size(); i++)
		{
			for (int j = 1; j <= S.size(); j++)
			{
				if (T[i-1] == S[j-1]) ta[i][j] = ta[i][j-1] + ta[i-1][j-1];
				else ta[i][j] = ta[i][j-1];
			}
		}
		return ta[T.size()][S.size()];
	}

//转置行和列的1维表动态规划法-优化
	int numDistinct(string S, string T) 
	{
		vector<int> ta(T.size()+1);
		int a = 0, b = 1;
		for (int i = 1; i <= S.size(); i++)
		{
			b = 1;
			for (int j = 1; j <= T.size(); j++)
			{
				a = ta[j];
				if (S[i-1] == T[j-1]) ta[j] += b;
				b = a;
				if (b == 0) break;
			}
		}
		return ta[T.size()];
	}

//神奇的通过的程序--逆向填表法
	int numDistinct2(string S, string T) {
		vector<int> ta(T.size()+1);
		ta[0] = 1;
		for (int i = 0; i < S.size(); i++)
		{
			for (int j = T.size()-1; j >= 0; j--)
			{
				ta[j+1] += (S[i]==T[j])*ta[j];
			}
		}
		return ta[T.size()];
	}

//2014-2-17 update
	int numDistinct(string S, string T) 
	{
		int *table = new int[T.length()+1];
		table[0] = 1;
		for (int i = 1; i <= T.length(); i++)
		{
			table[i] = 0;
		}
		for (int i = 0; i < S.length(); i++)
		{
			int j = i<T.length()?i:T.length();
			for (; j >= 0; j--)
			{
				if (T[j] == S[i]) table[j+1] += table[j];//把握全局，逆向填表
			}
		}
		return table[T.length()];
	}