【动态规划】【前缀和】：903DI序列的有效排列

本文涉及的基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频

动态规划汇总

LeetCode903DI序列的有效排列

给定一个长度为 n 的字符串 s ，其中 s[i] 是:

“D” 意味着减少，或者

“I” 意味着增加

有效排列是对有 n + 1 个在 [0, n] 范围内的整数的一个排列 perm ，使得对所有的 i：

如果 s[i] == ‘D’，那么 perm[i] > perm[i+1]，以及；

如果 s[i] == ‘I’，那么 perm[i] < perm[i+1]。

返回有效排列 perm的数量。因为答案可能很大，所以请返回你的答案对 109 + 7 取余。

示例 1：

输入：s = “DID”

输出：5

解释：

(0, 1, 2, 3) 的五个有效排列是：

(1, 0, 3, 2)

(2, 0, 3, 1)

(2, 1, 3, 0)

(3, 0, 2, 1)

(3, 1, 2, 0)

示例 2:

输入: s = “D”

输出: 1

分析

用动态规划解决，时间复杂度O(nnn)。用strRes表示结果串，用n表示它的长度，每个数字的取值范围[0,n)。dp[i][j]，表示前i+1个数已经处理，未处理的数中共有j个数大于strRes[i]。状态数共有n*n个，状态转换的时间复杂是O(n)。以上升为例：只需要考虑j个比strRes[i]数，选择最小的数，则jNew=j-1；选择次小的数， jNew=j-2…。下降类似，小于strRes[i]的数，可以计算出来：总数-已经处理的数-未处理的数中大于res[i]=n-(i+1)-j。注意：各位数各不相等，所以已经处理的数（如：res[i])是不会在出现的，所以未处理的数，需要考虑大于和小于，不需要考虑等于。

代码

template

class C1097Int

{

public:

C1097Int(long long llData = 0) :m_iData(llData% MOD)

{

}

C1097Int operator+(const C1097Int& o)const

{

return C1097Int(((long long)m_iData + o.m_iData) % MOD);

}

C1097Int& operator+=(const C1097Int& o)

{

m_iData = ((long long)m_iData + o.m_iData) % MOD;

return this;

}

C1097Int& operator-=(const C1097Int& o)

{

m_iData = (m_iData + MOD – o.m_iData) % MOD;

return this;

}

C1097Int operator-(const C1097Int& o)

{

return C1097Int((m_iData + MOD – o.m_iData) % MOD);

}

C1097Int operator(const C1097Int& o)const

{

return((long long)m_iData * o.m_iData) % MOD;

}

C1097Int& operator=(const C1097Int& o)

{

m_iData = ((long long)m_iData * o.m_iData) % MOD;

return *this;

}

bool operator<(const C1097Int& o)const

{

return m_iData < o.m_iData;

}

C1097Int pow(long long n)const

{

C1097Int iRet = 1, iCur = *this;

while (n)

{

if (n & 1)

{

iRet *= iCur;

}

iCur *= iCur;

n >>= 1;

}

return iRet;

}

C1097Int PowNegative1()const

{

return pow(MOD – 2);

}

int ToInt()const

{

return m_iData;

}

private:

int m_iData = 0;;

};

template

int operator+(int iData, const C1097Int& int1097)

{

int iRet = int1097.operator+(C1097Int(iData)).ToInt();

return iRet;

}

template

int& operator+=(int& iData, const C1097Int& int1097)

{

iData = int1097.operator+(C1097Int(iData)).ToInt();

return iData;

}

template

int operator*(int iData, const C1097Int& int1097)

{

int iRet = int1097.operator*(C1097Int(iData)).ToInt();

return iRet;

}

template

int& operator*=(int& iData, const C1097Int& int1097)

{

iData = int1097.operator*(C1097Int(iData)).ToInt();

return iData;

}

class Solution {
public:
	int numPermsDISequence(string s) {
		//n：结果串的长度 每个数字的取值范围[0,n)
		int n = s.length() + 1;
		vector<C1097Int> pre(n);//记录有多少个数大于当前数
		for (int i = 0; i < n; i++)
		{
			pre[n - i -1] += 1;
		}
		for (int i = 0; i < s.length(); i++)
		{
			vector<C1097Int> dp(n );
			if ('I' == s[i])
			{
				for (int iMore = 1; iMore < n; iMore++)
				{
					for (int j = 0; j < iMore; j++)
					{
						dp[iMore - j - 1] += pre[iMore];
					}
				}
			}
			else
			{
				for (int iMore = 0; iMore < n; iMore++)
				{
					const int less = n - (i + 1) - iMore;
					if (less < 1)
					{
						break;
					}
					for (int j = 0; j < less; j++)
					{
						const int iNewLess = less - j - 1;
						const int iNewMore = n - (i + 1 + 1) - iNewLess;
						dp[iNewMore] += pre[iMore];
					}
				}
			}
			pre.swap(dp);
		}
		auto bi = std::accumulate(pre.begin(), pre.end(), C1097Int(0));
		return bi.ToInt();
	}
};

测试用例

int main()

{

int res = Solution().numPermsDISequence(“”);

Assert(1, res);

res = Solution().numPermsDISequence(“I”);

Assert(1, res);

res = Solution().numPermsDISequence(“D”);

Assert(1, res);

res = Solution().numPermsDISequence(“II”);

Assert(1, res);

res = Solution().numPermsDISequence(“ID”);

Assert(2, res);

res = Solution().numPermsDISequence(“DD”);

Assert(1, res);

res = Solution().numPermsDISequence(“DI”);

Assert(2, res);

res = Solution().numPermsDISequence(“DID”);

Assert(5, res);

res = Solution().numPermsDISequence(“IDD”);

Assert(3, res);

res = Solution().numPermsDISequence(“DDI”);

Assert(3, res);

res = Solution().numPermsDISequence(“DII”);

Assert(3, res);

res = Solution().numPermsDISequence(“IDI”);

Assert(5, res);

res = Solution().numPermsDISequence(“IID”);

Assert(3, res);

//CConsole::Out(res);

}

优化

可以利用前缀和，将时间复杂度降到O(n*n)。


iMore取[1,…]中任意数，选择最大的数，则jNew都等于0
iMore取[2,…]中任意数，选择次大的数，则jNew都等于1
iMore取[3,…] 中任意数，选择第三大的数，则jNew都等于2
…
结论:
dp[0] = sum(pre[1]…pre[n-1])
dp[1] = sum(pre[2]…pre[n-1])
dp[2] = sum(pre[3]…pre[n-1])
…

代码

class Solution {
public:
	int numPermsDISequence(string s) {
		//n：结果串的长度 每个数字的取值范围[0,n)
		int n = s.length() + 1;
		vector<C1097Int> pre(n);//记录有多少个数大于当前数
		for (int i = 0; i < n; i++)
		{
			pre[n - i -1] += 1;
		}
		for (int i = 0; i < s.length(); i++)
		{
			vector<C1097Int> dp(n );
			if ('I' == s[i])
			{
				C1097Int biSum = 0;
				for (int j = n-1; j > 0 ; j-- )
				{
					biSum += pre[j];
					dp[j-1] = biSum;
				}
			}
			else
			{
				C1097Int biSum = 0;
				for (int j = n - 1; j > 0; j--)
				{//j是小于strRes[i]的数目
					const int iMore = n - (i + 1) - j;
					if (iMore < 0)
					{
						continue;
					}
					const int iNewMore = n - (i + 1+1) - (j-1);
					biSum += pre[iMore];
					dp[iNewMore] = biSum;
				}
			}
			pre.swap(dp);
		}
		auto bi = std::accumulate(pre.begin(), pre.end(), C1097Int(0));
		return bi.ToInt();
	}
};