【动态规划】数位DP的原理、模板（封装类）

本文涉及知识点

C++动态规划

复杂但相对容易理解的解法

上界、下界的位数一样都为N。如果不一样，拆分一样。比如：[10,200]，拆分[10,99]和[100,200]。由于要枚举到 1 ∼ N 1\sim N 1∼N，故实际复杂度是N倍。

动态规划的状态表示

dp[n][m][m1]，n表示已经处理最高n位，m表示上下界状态：0非上下界，1下界，2上界，3上下界。m1是自定义状态。
某题范围是[110,190]，处理一位后：1是上下界，无其它合法状态。处理二位后，11是下界，19是上界， 12 ∼ 18 12 \sim 18 12∼18是非上下界。
空间复杂度：O( 4 N 4N 4N)

动态规划的状态表示

第一层循环n从小到大；第二层循环m，任意顺序；第三层自定义状态。

动态规划的转移方程

单个状态的时间复杂度： ∑ \sum ∑。总时间复杂度：O(4N ∑ \sum ∑)

动态规划的初始值

枚举最高位。

动态的返回值

dp.back() 和自定义状态有关。

优化一

如果上下界没有公共前缀，则不存在状态上下界。
如果公共前缀为len，则目标串的前n位必定和上下界相同。故可以不处理 0 ∼ n − 1 0 \sim n-1 0∼n−1，直接从第n位开始处理。

优化二

[ l e f t ∼ r ] 的方案数 = [ 0 ∼ r ] 的方案数 − [ 0 ∼ l e f t − 1 ] 的方案数 = [ 0 ∼ r ] 的方案数 − [ 0 ∼ l e f t ] 的方案数 + l e f t 是否符合 [left \sim r]的方案数 =[0 \sim r]的方案数-[0\sim left-1]的方案数=[0 \sim r]的方案数-[0\sim left]的方案数 + left是否符合 [left∼r]的方案数=[0∼r]的方案数−[0∼left−1]的方案数=[0∼r]的方案数−[0∼left]的方案数+left是否符合。简化后只需要考虑是否是上限。

优化三

小于N位的数，可以可以看成前导0。

自己摸索的封装类

template<classELE,classResultType, ELE minEle, ELE maxEle>classCLowUperr{public:CLowUperr(int iCustomStatusCount):m_iCustomStatusCount(iCustomStatusCount){}voidInit(const ELE* pLower,const ELE* pHigh,int iEleCount){ m_vPre.assign(4, vector<ResultType>(m_iCustomStatusCount));if(iEleCount <=0){return;}InitPre(pLower, pHigh); iEleCount--;while(iEleCount--){ pLower++; pHigh++; vector<vector<ResultType>>dp(4, vector<ResultType>(m_iCustomStatusCount));OnInitDP(dp);//处理非边界for(auto tmp = minEle; tmp <= maxEle; tmp++){OnEnumOtherBit(dp[0], m_vPre[0], tmp);}//处理下边界OnEnumOtherBit(dp[1], m_vPre[1],*pLower);for(auto tmp =*pLower +1; tmp <= maxEle; tmp++){OnEnumOtherBit(dp[0], m_vPre[1], tmp);}//处理上边界OnEnumOtherBit(dp[2], m_vPre[2],*pHigh);for(auto tmp = minEle; tmp <*pHigh; tmp++){OnEnumOtherBit(dp[0], m_vPre[2], tmp);}//处理上下边界if(*pLower ==*pHigh){OnEnumOtherBit(dp[3], m_vPre[3],*pLower);}else{OnEnumOtherBit(dp[1], m_vPre[3],*pLower);for(auto tmp =*pLower +1; tmp <*pHigh; tmp++){OnEnumOtherBit(dp[0], m_vPre[3], tmp);}OnEnumOtherBit(dp[2], m_vPre[3],*pHigh);} m_vPre.swap(dp);}} ResultType Sum(int iMinMask,int iMaxMask)const{ ResultType iRet =0;for(int status =0; status <4; status++){for(int mask = iMinMask; mask <= iMaxMask; mask++){ iRet += m_vPre[status][mask];}}return iRet;}protected:constint m_iCustomStatusCount;virtualvoidOnEnumOtherBit(vector<ResultType>& dp,const vector<ResultType>& vPre, ELE curValue)=0;virtualvoidOnEnumFirstBit(vector<ResultType>& vPre,const ELE curValue)=0;virtualvoidOnInitDP(vector<vector<ResultType>>& dp){} vector<vector<ResultType>> m_vPre;private:voidInitPre(const ELE*const pLower,const ELE*const pHigh){for(ELE cur =*pLower; cur <=*pHigh; cur++){int iStatus =0;if(*pLower == cur){ iStatus =*pLower ==*pHigh ?3:1;}elseif(*pHigh == cur){ iStatus =2;}OnEnumFirstBit(m_vPre[iStatus], cur);}}};

参考通用模板：动态规划之记忆化搜索

Rec(i,bUpper)
返回值：bUpper，当前数据的前i位和上界是否相同。有两种解释：一，前i位自定义状态为m的方案数。二，后N-i位自定义状态m的方案数。大部分题，两种解释都行得通。
dp[i] = Rec(i,false)。
任意Rec(i,true) 只会被调用一次，故无需缓存。
令上界是数字n，N = logn,即n的位。
状态数：N。 每个状态的时间复杂度O( ∑ \sum ∑)。故总复杂度：O( ∑ \sum ∑N)。 1 ∼ N − 1 1 \sim N-1 1∼N−1位可以直接通过dp计算，故处理 1 ∼ N − 1 1 \sim N-1 1∼N−1的时间可以忽略。

回调类

template<classELE,classResultType>classIUpperDPCall{public:virtualvoidOnEnum(int n,vector<ResultType>& dp,const vector<ResultType>& vNext, ELE curValue,int iCustomStatusCount)=0;virtualvoidOnInitEnd(vector<ResultType>& dp, vector<ResultType>& upDp)=0;};

OnInitEnd：
dp= m_vDP[n]和dpUp=m_vDpUpper[n]。dp[m]和dpUp[m]表示自定义状态为m的方案数。
OnEnum有以下三种情况，三者的逻辑是一样的，故实现时无需考虑是那种情况。
情况一：dp=m_vDP[n],vNext=m_vDP[n+1]
情况二:dp=m_vDpUpper[n],vNext=m_vDpUpper[n+1]
情况三：dp=m_vDpUpper[n],vNext=m_vDP[n+1]
curValue当前元素的值。
iCustomStatusCount 自定义状态的数量。

最高位的取值范围和其它位相同

比如：枚举字母，容许前导0,即N-1位可以看成有一个前导0的N位数。

template<classELE,classResultType>classCUperrDP{public:CUperrDP(int iCustomStatusCount, IUpperDPCall<ELE, ResultType>& call, ELE minEle, ELE maxEle):m_iCustomStatusCount(iCustomStatusCount),m_call(call),m_minEle(minEle),m_maxEle(maxEle){}voidInit(const ELE* pHigh,int iEleCount){ m_vDP.assign(iEleCount +1, vector<ResultType>(m_iCustomStatusCount)); m_vDpUpper = m_vDP; m_call.OnInitEnd(m_vDP.back(), m_vDpUpper.back());//预处理增加的一位for(int i = iEleCount -1;i >0;i--){ m_call.OnEnum(i,m_vDpUpper[i], m_vDpUpper[i +1], pHigh[i],m_iCustomStatusCount);for(auto j = m_minEle; j < pHigh[i];j++){ m_call.OnEnum(i,m_vDpUpper[i], m_vDP[i +1], j, m_iCustomStatusCount);}for(auto j = m_minEle; j <= m_maxEle;j++){ m_call.OnEnum(i,m_vDP[i], m_vDP[i +1], j, m_iCustomStatusCount);}} m_call.OnEnum(0,m_vDpUpper[0], m_vDpUpper[1], pHigh[0], m_iCustomStatusCount);for(auto j = m_minEle; j < pHigh[0];j++){ m_call.OnEnum(0,m_vDP[0], m_vDP[1], j, m_iCustomStatusCount);}} ResultType Sum(int iMinCustomStatu,int iMaxCustomStatu){ ResultType ret =0;for(int i = iMinCustomStatu; i <= iMaxCustomStatu;i++){ ret += m_vDP[0][i]+ m_vDpUpper[0][i];}return ret;} ResultType Sum(){returnSum(0, m_iCustomStatusCount -1);} vector<vector<ResultType>> m_vDP, m_vDpUpper;const ELE m_minEle, m_maxEle;protected:constint m_iCustomStatusCount; IUpperDPCall<ELE, ResultType>& m_call;};

ELE：元素的类型，几乎全部是char。
ResultType：记录方案数量的类型，如果：int,long long,自定义数据类型。
minEle：最小元素
maxEle：最大元素。
pHigh, int iEleCount：上限字符串的数量和长度。
Init的大致逻辑：
一，初始化。
二，n = N-1 to 1。如果当前元素等于pHigh[n],dpUp[n]对应dpUp[n+1];如果当前元素小于pHigh[n]，dpUp[n]对应dpUp[n+1];任意当前元素,dp[n]对应dp[n+1]。
三，第0个元素等于pHigh[0]，则dpUp[0]对应dpUp[1]。第0个元素小于pHigh[0]，则dp[0]对应dp[1]。

最高位的取值范围和其它位不同

如：正整数不能以0开始。原理类似上一部分，只描述不同点：
firstMinEle，最高位最小元素。
m_vFirstDP[n][m]:N-n位数，自定义状态为m的方案数。 m_vFirstDP[N]未使用。

template<classELE,classResultType>classCUperrDP2{public:CUperrDP2(int iCustomStatusCount, IUpperDPCall<ELE, ResultType>& call, ELE minEle, ELE maxEle, ELE firstMinEle):m_iCustomStatusCount(iCustomStatusCount),m_call(call),m_minEle(minEle),m_maxEle(maxEle),m_firstMinEle(firstMinEle){}voidInit(const ELE* pHigh,int iEleCount){ m_vDP.assign(iEleCount +1, vector<ResultType>(m_iCustomStatusCount)); m_vDpUpper = m_vDP; m_vFirstDP = m_vDP; m_call.OnInitEnd(m_vDP.back(), m_vDpUpper.back());//预处理增加的一位for(int i = iEleCount -1;i >0;i--){ m_call.OnEnum(i,m_vDpUpper[i], m_vDpUpper[i +1], pHigh[i], m_iCustomStatusCount);for(auto j = m_minEle; j < pHigh[i];j++){ m_call.OnEnum(i,m_vDpUpper[i], m_vDP[i +1], j, m_iCustomStatusCount);}for(auto j = m_minEle; j <= m_maxEle;j++){ m_call.OnEnum(i,m_vDP[i], m_vDP[i +1], j, m_iCustomStatusCount);}for(auto j = m_firstMinEle; j <= m_maxEle;j++){ m_call.OnEnum(i,m_vFirstDP[i], m_vDP[i +1], j, m_iCustomStatusCount);}} m_call.OnEnum(0,m_vFirstDP[0], m_vDpUpper[1], pHigh[0], m_iCustomStatusCount);for(auto j = m_firstMinEle; j < pHigh[0];j++){ m_call.OnEnum(0,m_vFirstDP[0], m_vDP[1], j, m_iCustomStatusCount);}} ResultType Sum(int iMinCustomStatu,int iMaxCustomStatu){ ResultType ret =0;for(int i =0;i +1< m_vFirstDP.size();i++){ ret +=accumulate(m_vFirstDP[i].begin()+ iMinCustomStatu, m_vFirstDP[i].begin()+ iMaxCustomStatu +1,(ResultType)0);}return ret;} ResultType Sum(){returnSum(0, m_iCustomStatusCount -1);} vector<vector<ResultType>> m_vDP, m_vDpUpper,m_vFirstDP; ELE m_minEle, m_maxEle, m_firstMinEle;protected:constint m_iCustomStatusCount; IUpperDPCall<ELE, ResultType>& m_call;};

样例

力扣

洛谷

扩展阅读

视频课程

先学简单的课程，请移步ZEEKLOG学院，听白银讲师（也就是鄙人）的讲解。
https://edu.ZEEKLOG.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.ZEEKLOG.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。