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

Distinct Subsequences

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.

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

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

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

//最好理解的二维动态规划法，一次性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()];
	}

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

原文：http://blog.csdn.net/kenden23/article/details/19332545