本文涉及的基础知识点
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
题目
给定一个长度为 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(); } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 鄙人想对大家说的话
|
|-|
|闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。|
| 墨家名称的来源：有所得以墨记之。 |
|如果程序是一条龙，那算法就是他的是睛|
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
