【动态规划】【子数组划分】【前缀和】1977. 划分数字的方案数

作者推荐

【动态规划】【状态压缩】【2次选择】【广度搜索】1494. 并行课程 II

本文涉及知识点

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

LeetCode1977 划分数字的方案数

你写下了若干正整数，并将它们连接成了一个字符串 num 。但是你忘记给这些数字之间加逗号了。你只记得这一列数字是非递减的且没有任何数字有前导 0 。
请你返回有多少种可能的正整数数组可以得到字符串 num 。由于答案可能很大，将结果对 109 + 7 取余后返回。

示例 1：
输入：num = “327”
输出：2
解释：以下为可能的方案：
3, 27
327
示例 2：
输入：num = “094”
输出：0
解释：不能有数字有前导 0 ，且所有数字均为正数。
示例 3：
输入：num = “0”
输出：0
解释：不能有数字有前导 0 ，且所有数字均为正数。
示例 4：
输入：num = “9999999999999”
输出：101
提示：
1 <= num.length <= 3500
num 只含有数字 ‘0’ 到 ‘9’ 。

动态规划

动态规划的状态表示

dp[i][j] 表示num[0,i)组成的子序列，且最后一个元素长度为j 的数量。

动态规划的转移方程

枚举最最后一个元素的长度
dp[i+k][k] = $\Large\sum_{m:0}^{k-1}$ (pre[i][m]) 可以用前缀和优化。
如果nums(i-k,i] 小于等于nums[i,i+k) 则加上pre[i][k]，可以用最长公共前缀预处理，预处理时间复杂度：O(nn)。
如果没有上面的两个优化，时间复杂度高达：O(n⁴)。
如果nums[i]为’0’，忽略。

动态规划的初始值

pre[0][0]=1 其它为0。

动态规划的转移方程

i从0到大。前置条件转移后置条件。

动态规划返回值

pre.back()之和。

代码

核心代码

//最长公共前缀(Longest Common Prefix)
class CLCP
{
public:CLCP(const string& str1, const string& str2){m_dp.assign(str1.length() , vector<int>(str2.length()));//str1[j...)和str2[k...]比较时, j和k不断自增，总有一个先到达末端for (int i = 0; i < str1.length(); i++){//枚举str2 先到末端 str1[i]和str2.back对应m_dp[i][str2.length() - 1] = (str1[i] == str2.back());for (int j = i-1 ; j >= 0 ; j-- ){const int k = str2.length() - 1 - (i-j);if (k < 0){break;}if (str1[j] == str2[k]){m_dp[j][k] = 1 + m_dp[j + 1][k + 1];}}			}for (int i = 0; i < str2.length(); i++){//枚举str1 先到末端 str2[i]和str1.back对应m_dp[str1.length()-1][i] = (str1.back() == str2[i]);for (int j = i - 1; j >= 0; j--){const int k = str1.length() - 1 - (i-j);if (k < 0){break;}if (str1[k] == str2[j]){m_dp[k][j] = 1 + m_dp[k + 1][j + 1];}}}}vector<vector<int>> m_dp;
};template<int MOD = 1000000007>
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;;
};class Solution {
public:int numberOfCombinations(string num) {m_c = num.length();CLCP lcp(num, num);vector<vector<C1097Int<> >> dp(m_c + 1, vector<C1097Int<> >(m_c + 1));dp[0][0] = 1;for (int i = 0; i < m_c; i++){if ('0' == num[i]){continue;}C1097Int biSum = 0;for (int j = 1; i + j <= m_c; j++){biSum += dp[i][j - 1];dp[i + j][j] += biSum;bool bMoreEqual = false;if ((i >= j)){const int len = lcp.m_dp[i][i - j];if (len  >= j){bMoreEqual = true;}else{bMoreEqual = num[i + len] > num[i - j + len];}}if (bMoreEqual){dp[i + j][j] += dp[i][j];}}}return std::accumulate(dp.back().begin(), dp.back().end(), C1097Int()).ToInt();}int m_c;
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}}int main()
{	string num;{Solution sln;num = "327";auto res = sln.numberOfCombinations(num);Assert(res,2);}{Solution sln;num = "094";auto res = sln.numberOfCombinations(num);Assert(res, 0);}{Solution sln;num = "0";auto res = sln.numberOfCombinations(num);Assert(res, 0);}{Solution sln;num = "9999999999999";auto res = sln.numberOfCombinations(num);Assert(res, 101);}
}

2023年2月

class C1097Int
{
public:
C1097Int(int iData = 0) :m_iData(iData)
{
}
C1097Int operator+(const C1097Int& o)const
{
return C1097Int(((long long)m_iData + o.m_iData) % s_iMod);
}
C1097Int& operator+=(const C1097Int& o)
{
m_iData = ((long long)m_iData + o.m_iData) % s_iMod;
return this;
}
C1097Int operator(const C1097Int& o)const
{
return((long long)m_iData o.m_iData) % s_iMod;
}
C1097Int& operator=(const C1097Int& o)
{
m_iData =((long long)m_iData *o.m_iData) % s_iMod;
return *this;
}
bool operator<(const C1097Int& o)const
{
return m_iData < o.m_iData;
}
C1097Int& pow( int n)const
{
C1097Int iRet = 1, iCur = *this;
while (n)
{
if (n & 1)
{
iRet *= iCur;
}
iCur *= iCur;
n >>= 1;
}
return iRet;
}
C1097Int PowNegative1()
{
return pow(s_iMod - 2);
}
int ToInt()const
{
return m_iData;
}
private:
int m_iData = 0;;
static const int s_iMod = 1000000007;
};

int operator+(int iData, const C1097Int& int1097)
{
int iRet = int1097.operator+(C1097Int(iData)).ToInt();
return iRet;
}

int& operator+=(int& iData, const C1097Int& int1097)
{
iData = int1097.operator+(C1097Int(iData)).ToInt();
return iData;
}

int operator*(int iData, const C1097Int& int1097)
{
int iRet = int1097.operator*(C1097Int(iData)).ToInt();
return iRet;
}

int& operator*=(int& iData, const C1097Int& int1097)
{
iData = int1097.operator*(C1097Int(iData)).ToInt();
return iData;
}

template
void MinSelf(T* seft, const T& other)
{
*seft = min(*seft, other);
}

template
void MaxSelf(T* seft, const T& other)
{
*seft = max(*seft, other);
}

int GetNotRepeateNum(int len, int iHasSel)
{
if (0 == len)
{
return 1;
}
if ((0 == iHasSel) && (1 == len))
{
return 10;
}
int iRet = 1;
if (iHasSel > 0)
{
for (int tmp = 10 - iHasSel; (tmp >= 2)&& len ; tmp–,len–)
{
iRet *= tmp;
}
}
else
{
iRet *= 9;
len–;
for (int tmp=9; (tmp>=2)&&len; len–,tmp–)
{
iRet *= tmp;
}
}
return iRet;
}

int GCD(int n1, int n2)
{
int t1 = min(n1, n2);
int t2 = max(n1, n2);
if (0 == t1)
{
return t2;
}
return GCD(t2%t1, t1);
}

void CreateMaskVector(vector& v,const int* const p,int n )
{
const int iMaxMaskNum = 1 << n;
v.resize(iMaxMaskNum);
for (int i = 0; i < n; i++)
{
v[1 << i] = p[i];
}
for (int mask = 1; mask < iMaxMaskNum ; mask++)
{
const int iSubMask = mask&(-mask);
v[mask] = v[iSubMask] + v[mask-iSubMask];
}
}

class Solution {
public:
int numberOfCombinations(string num) {
m_c = num.size();
if (‘0’ == num.begin())
{
return 0;
}
m_vDpCmpStr.assign(m_c, vector(m_c));
for (int i = m_c-1 ; i >=0 ; i–)
{
for (int j = m_c - 1; j >= 0; j-- )
{
if (num[i] != num[j])
{
continue;
}
m_vDpCmpStr[i][j] = 1;
if ((i + 1 < m_c) && (j + 1 < m_c))
{
m_vDpCmpStr[i][j] += m_vDpCmpStr[i + 1][j + 1];
}
}
}
vector<vector> dp(m_c, vector(m_c));
dp[0].assign(m_c, 1);
for (int iPos = 1; iPos < m_c; iPos++)
{
if ((‘0’ == num[iPos]) /&& (1 != len)*/)
{
continue;
}
int preLen = 1;
C1097Int sum(0);
for (int end = iPos; end < m_c; end++)
{
const int len = end - iPos + 1;
for (int i = 0; i < 2; i++)
{
const int iPrePos = iPos - preLen;
if (iPrePos >= 0)
{
const int iPubLen = m_vDpCmpStr[iPrePos][iPos];
bool Less = (preLen == len) && ((iPubLen >= len) || (num[iPrePos + iPubLen] < num[iPos + iPubLen] ));
if ((preLen < len) || Less )
{
preLen++;
sum += dp[iPrePos][iPos - 1];
}
}
}
dp[iPos][end] += sum;
}
}
C1097Int intSum;
for (const auto& d : dp)
{
intSum += d.back();
}
return intSum.ToInt();
}
int m_c;
vector<vector> m_vDpCmpStr;
};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛