問題描述：ios
通常體現爲，定義某種性質K，問某區間內具備K性質的數的個數算法
每每給的區間會很大，對區間內的每一個數進行判斷顯然會超時數組
因而數位DP登場學習
數位DP，顧名思義，是對數字的每一位進行DPspa
心得體會：.net
1.數位DP須要較爲熟練的記憶化搜索做爲基礎，雖然有的題能夠直接用循環進行狀態轉移，但記憶化搜索的狀態轉移更經常使用更容易理解code
2.時刻記住：abcd這個四位數 = a*1000+b*100+c*10+dblog
3.關於dp狀態的保存，通常一維都是保存數字在整個數中的位置（數位），而後根據題目給定的數字的性質肯定二維三維要保存什麼狀態遞歸
感受數位DP的關鍵就在於狀態的保存（固然狀態轉移也很重要）通常而言，dp[i][j][k]表達的信息是：具備i性質，j性質，k性質的數的個數字符串
4.在記憶化搜索的過程當中，對於數字abcd，搜索是從左往右搜索，但實際上計算是從右往左計算的（遞歸原理）
5.數位DP須要注意所搜索的範圍不能大於本來被視做字符串的那個數字（這個在記憶化搜索中常表現爲一個變量標記上界）
同時有時候0的狀況也須要特別注意（具體狀況具體分析吧）
6.數位DP剛剛入門的時候以爲很難，作多了以爲萬變不離其宗，代碼長得都差很少，都是套路，惟一的變化也就是定義的數的屬性不同
因此感受數位DP的難點也就是狀態的保存，針對題目給的性質保存相應的狀態
7.剛開始寫數位DP的時候用循環寫狀態轉移，感受理解起來沒有記憶化搜索清晰，因而後面都是用記憶化搜索寫的了
8.理論再強大，理解再深入，不如多作題，作第一道題的時候感受似懂非懂，後面作着作着也就漸漸理解了，書讀百遍其義自見也是這個理
玩了一個數位DP的專題：打開專題
終於作完了數位DP的專題，不過也只是初窺門檻，之後還要繼續努力^_^
總體看起來，代碼其實大體都一個套路，都是一個dfs 記憶化搜索，一個cal計算
數位DP通常都是用數組的維度保存數的性質，而後dp的值表示具備這樣性質的數的個數
我的以爲記憶化搜索比迭代好理解代碼看着也舒服，全部除了第一次寫的D題，其餘都是用記憶化寫的而後說說這個專題，CD兩題算是基礎題，G題定義的數字的性質蠻新穎，可是想到怎麼保存狀態也是基礎題
H題在基礎上加了倍數的判斷
AB兩題在狀態的保存上轉了點彎，特別是B題還結合了狀態壓縮和最長上升子序列
F題比較特別，求的不是數的個數，而是全部知足性質的數的平方和
E題也是數位，不過保存的是二進制數的每一位
（專題總體寫下來收穫蠻大的^_^）
題意：
定義beautiful 數：這個數能被它的每一位整除
例如12 能被1、2整除，故12是beautiful數
求區間[l,r]內的beautiful數的個數
分析：
利用記憶化搜索把小於等於num 的數中的全部beautiful數都搜出來
怎麼搜呢？仍是按照數字「位」來搜。
如今問題是：
1.怎麼判斷beautiful數？
2.怎麼保存狀態？
顯然，須要將beautiful數的性質用狀態保存下來。
beautiful數須要整除它全部的非零位
那麼它只需整除它全部位的最小公倍數便可
數字1~9的最小公倍數爲2520（設爲mxlcm）
考慮這樣一種保存狀態的方法：
dp[i][j][k]表示長度爲 i，全部數位的lcm爲j模mxlcm餘k的答案
那麼須要開一個dp[20][2520][2520]的數組，類型是long long
這數組顯然是開不下的，要想辦法壓縮
對這個數組的第二維，「全部數位的lcm爲j」，其實j的取值雖然可能達到2520
可是j實際的數最多隻有50個
因而能夠考慮開一個hs數組，hs[j] = id;表示給全部數位的lcm爲j的編號爲id
這樣一個dp[20][50][2520]的數組保存狀態，那麼萬事俱備能夠搜索了。
搜索的具體方法在代碼中介紹
代碼：
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
/*
若一個數能整除它的全部的非零數位，
那麼至關於它能整除個位數的最小公倍數。
所以記憶化搜索中的參數除了len(當前位)和up（是否達到上界），
有一個prelcm表示前面的數的最小公倍數，
判斷這個數是不是Beautiful Numbers，還要有一個參數表示前面數，
可是這個數太大，須要縮小它的範圍。
縮小前面組成的數的範圍:
能夠發現全部個位數的最小公倍數是2520，假設當前的Beautiful Numbers是x，
那麼 x % lcm{dig[i]} = 0,
又 2520%lcm{dig[i]} = 0，
那麼x%2520%lcm{ dig[i] } = 0，x範圍由9*10^18變爲2520。
*/
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b)
{
return a/gcd(a,b)*b;
}
const int mxlcm = 2520;// 0~9全部數字的 lcm
int dig[25];//保存數字的每一位
ll dp[25][50][mxlcm+5];//dp[i][j][k]表示長度爲 i 全部數字lcm爲j %mxlcm 爲 k(即餘數爲k)的數的個數
int hs[mxlcm+5];//hs[i]表示全部數位的lcm 爲 i的數的編號
/*
關於上界 up 的做用：
好比數字是 543
那麼當搜到 5 的時候
枚舉 0~5 其中枚舉 4 的時候能夠去搜49九、
可是枚舉到 5 的時候 599 是大於543的
因此這裏用 up 控制搜索到的數字在 cal計算的數字範圍內
*/
ll dfs(int len,int plcm,int pnum,bool up)//記憶化搜索
{ //當前位 前面數字的lcm 前面的數 是否達到上界
if (len == 0) return pnum%plcm == 0;//整個數都搜完了，即搜到個位，只需單獨判斷個位便可
if (!up&&dp[len][hs[plcm]][pnum]!=-1) return dp[len][hs[plcm]][pnum];
int n = 9;
if (up)//到界了
{
n = dig[len];//達到上界的時候是dig[len],其餘時候是9
}
ll ans = 0;
for (int i = 0;i <= n;++i)//枚舉這一位可能的數字
{
int nnum = (pnum*10 + i)%mxlcm;
int nlcm = plcm;
if (i) nlcm = lcm(plcm,i);
ans += dfs(len-1,nlcm,nnum,up&&(i == n));//全部的可能加起來
}
if (!up) dp[len][hs[plcm]][pnum] = ans;
return ans;
}
ll cal(ll x)//計算[1,num]中beautifun的個數
{
int len = 0;//將數字的每一位保存在數組dig中
while (x)
{
dig[++len] =x%10;
x/=10;
}
return dfs(len,1,0,1);//傳參
}
void init()//hash預處理
{
int id = 0;mem(dp,-1);//記憶化dp只初始化一次便可
for (int i = 1;i <= mxlcm;++i)
{
if (mxlcm%i == 0) hs[i] = ++id;
}
}
int main()
{
int T;init();
scanf("%d",&T);
while (T--)
{
ll l,r;
scanf("%I64d %I64d",&l,&r);
printf("%I64d\n",cal(r) - cal(l-1));
}
return 0;
}
題意：
當把數當字符串看的時候，求區間[l,r]最長公共子序列的長度爲K的數的個數
我我的以爲這題出的很好，將數位DP，狀態壓縮和最長公共子序列的nlogn算法結合起來
另寫了題解： HDU 4352 XHXJ's LIS(數位DP+狀壓)
題意：
區間[l,r]內數字的數位不含62且不含4的數的個數
分析：
這題數據小，能夠水過，用dp[i]表示前i個數中知足的數的個數
if ok(i) dp[i] = dp[i-1] + 1 else dp[i] = dp[i-1] 先求出全部dp，而後直接輸入輸出
用正常的數位DP的方法寫的話：
狀態保存：
dp[len][0]表示長度爲len 且不含4和62，最高位不是2的個數
dp[len][1]表示長度爲len 且不含4和62，最高位是2的個數
狀態轉移：
dp[i][0] = 8*dp[i-1][0] + dp[i-1][1] (除去4還有8種可能)
dp[i][1] = 7*dp[i-1][1] + dp[i-1][1] (除去4還要除去6，不然會構成62)
正常的循環能夠寫，不過感受記憶化搜索更好理解寫着更清晰，故而用記憶化寫的
代碼：
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
using namespace std;
typedef long long ll;
/*
狀態保存：
dp[len][0]表示長度爲len 且不含4和62，最高位不是2的個數
dp[len][1]表示長度爲len 且不含4和62，最高位是2的個數
狀態轉移：
dp[i][0] = 8*dp[i-1][0] + dp[i-1][1] (除去4還有8種可能)
dp[i][1] = 7*dp[i-1][1] + dp[i-1][1] (除去4還要除去6，不然會構成62)
*/
int dp[10][2];
int dig[10];//保存數字的每一位
int dfs(int len,bool is6,bool up)//當前搜的位，這一位的前一位是否是6，是否爲上界
{
if (len == 0) return 1; //dp[0][0] = 1;
if (!up&&dp[len][is6]!=-1) return dp[len][is6];
int ans = 0;
int n = 9;if (up) n = dig[len];
for (int i = 0;i <= n;++i)
{
if (i==4) continue;// 4
if (is6&&i==2) continue;// 62
ans += dfs(len-1,i==6,up&&(i == n));
}
if (!up) dp[len][is6] = ans;
return ans;
}
int cal(int x)
{
int len = 0;
while (x)
{
dig[++len] = x%10;
x/=10;
}
return dfs(len,0,1);
}
int main()
{
mem(dp,-1);
int l,r;
while (scanf("%d %d",&l,&r)&&(l||r))
{
printf("%d\n",cal(r)-cal(l-1));
}
return 0;
}
本渣的第一道數位DP題，對着別人的題解啃了半天，用循環來進行狀態轉移
（後來深入體會到記憶化搜索寫着更清晰更好理解！）
題意：
區間[1,r]中數位不含49的數的個數（感受數位DP的題意都是一個調調）
分析：
dp[i][0] 表示長度爲 i 的數中 不含 49 的數的個數
dp[i][1] 表示長度爲 i 的數中 不含 49 但最高位爲 9 的數的個數
dp[i][2] 表示長度爲 i 的數中 含49的數的個數
dp[i][0] = dp[i-1][0] * 10 - dp[i-1][1];
dp[i][1] = dp[i-1][0];
dp[i][2] = dp[i-1][2] * 10 + dp[i-1][1];
先把表打好，而後對於具體輸入的r具體處理
代碼1（循環）：
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 20;
ll dp[N][3];
void init()
{
dp[0][0] = 1;
for (int i = 1;i <= N;++i)
{
dp[i][0] = dp[i-1][0] * 10 - dp[i-1][1];
dp[i][1] = dp[i-1][0];
dp[i][2] = dp[i-1][2] * 10 + dp[i-1][1];
}
}
int len;
ll s[30];
void cal(ll x)
{
len = 0;
while (x)
{
s[++len] = x%10;
x/=10;
}
}
int main()
{
int T;scanf("%d",&T);
init();
while (T--)
{
ll n;
scanf("%I64d",&n);
++n;cal(n);
int lr = 0;ll sun = 0;bool fd = 0;
for (int i = len;i >= 1;--i)
{
sun += (ll)(s[i])*dp[i-1][2];
if (fd) sun += (ll)(s[i])*(dp[i-1][0]);
if (!fd&&s[i] > 4)
{
sun += dp[i-1][1];
}
if (lr == 4&&s[i] == 9) fd = 1;
lr = s[i];
}
printf("%I64d\n",sun);
}
return 0;
}
代碼2（記憶化搜索）：
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
#define Sint(n) scanf("%d",&n)
#define Sll(n) scanf("%I64d",&n)
#define Schar(n) scanf("%c",&n)
#define Sint2(x,y) scanf("%d %d",&x,&y)
#define Sll2(x,y) scanf("%I64d %I64d",&x,&y)
#define Pint(x) printf("%d",x)
#define Pllc(x,c) printf("%I64d%c",x,c)
#define Pintc(x,c) printf("%d%c",x,c)
using namespace std;
typedef long long ll;
/*
記憶化絕對比循環好理解，我發誓~~~^_^
dp[len][four][have]表示正在處理的位長度爲len
正在處理的前面一位是否是4
已經處理過的位裏面是否是已經有49了
*/
ll dp[22][2][2];
int dig[22];
ll dfs(int len,bool four,bool have,bool up)
{
if (len == 0) return have;
ll &ot = dp[len][four][have];
if (!up&&~ot) return ot;
int n = 9;if (up) n = dig[len];
ll ans = 0;
for (int i = 0;i <= n;++i)
{
bool newhave = have;
if (four&&i == 9) newhave = 1;
ans += dfs(len-1,i==4,newhave,up&&i==n);
}
if (!up) ot = ans;
return ans;
}
ll cal(ll x)
{
int len = 0;
while (x)
{
dig[++len] = x%10;
x/=10;
}
return dfs(len,0,0,1);
}
int main()
{
mem(dp,-1);
int T;Sint(T);
while (T--)
{
ll n;Sll(n);
Pllc(cal(n),'\n');
}
return 0;
}
題意：求區間[l,r]內二進制數中0比1多的數的個數
分析：以前作的都是十進制數的數位DP，這個能夠轉換成二進制數的數位DP（花神的數論題也是二進制上的數位DP）
dp[i][j][k]中i,j,k分別表示長度，0的個數，1的個數，記憶化搜索的時候多傳的兩個參數分別表示是否到達上界，前一位是否爲0
代碼：
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
using namespace std;
typedef long long ll;
int dig[70];
ll dp[70][70][70];//長度 0的個數 1的個數
ll dfs(int len,int zero ,int one,bool up,bool z)
{
if (len == 0)
{
return z||(zero>=one);
}
ll &ot = dp[len][zero][one];
if (!up&&!z&&ot!=-1) return ot;
int n = 1;if (up) n = dig[len];
ll ans = 0;
for (int i = 0;i <= n;++i)
{
if (z&&i==0) ans += dfs(len-1,0,0,up&&(i==n),z&&(i==0));
else ans += dfs(len-1,zero + (!i),one+i,up&&(i==n),z&&(i==0));
}
if (!up&&!z) ot = ans;
return ans;
}
ll cal(ll x)
{
int len = 0;
while (x)
{
dig[++len] = x%2;
x/=2;
}
return dfs(len,0,0,1,1);
}
int main()
{
ll l,r;mem(dp,-1);
while (scanf("%lld %lld",&l,&r) == 2)
{
printf("%lld\n",cal(r)-cal(l-1));
}
return 0;
}
這個題目不一樣於通常的數位DP求區間內具備某性質的數的個數，而是求區間內具備某性質的全部數的平方和
感受蠻厲害的樣子，另寫了題解： HDU 4507 吉哥系列故事——恨7不成妻(數位DP)
題意：
求區間[l,r]內的平衡數的個數
所謂平衡數是指，把這個數的某一數位設置爲支點。支點左右兩邊按|i - p|*dig計算力矩，若是能找到支點使左右力矩相等就是平衡數
例如4139 取3爲支點，左邊力矩 = 4*2+1*1 = 9，右邊力矩 = 9*1 = 9全部是平衡數
分析：
仍是根據數的性質保存狀態，顯然數的性質涉及到力矩，支點的位置
因此dp[i][j][k] :
i : 正在處理的數位
j : 支點的位置
k : 左右力矩之和(正負算，爲 0 就是平衡的)
dp[i][j][k]就是具備上述性質的數的個數
dp[i][j][k] = dp[i-1][j][ k + dig*(i-j)]
其中 dig 爲數位 i 處枚舉的可能的數字
狀態轉移中j沒有轉移？支點的位置須要另外枚舉
枚舉支點位置？會不會出現算某個位置的時候算了一遍數字x，算另外一個位置的時候又算了一遍x這樣算重複的狀況？
想一下，一個數若是是平衡數，那麼它的支點位置必然是固定的（0除外）
因此不會算重複，只有最後把重複的0減去就好，0算了len遍，故重複的0有（len-1）個
這裏提一個事，這題的dp[i][j][k]保存了3個維度的信息，可是實際上，它在狀態轉移的時候第二維的j並無改變
看代碼裏面的dfs的過程也是，傳入的一個參數p歷來都沒有變過，爲何不省去這一維呢？
首先，dfs的時候確實能夠不傳參數p,直接讓其在全局裏面，而後枚舉位置的時候改變其值，每次遞歸的時候能夠直接用
可是dp仍是應該保存這一維，由於題目是多組數據，秉着算過就記錄下來的原理，能夠爲後面更多組數節約時間
前面B題裏面也有一維沒有參與狀態轉移，可是依舊保存下來了是一樣的原理（B題的dfs沒有傳那個不變的參數K）
代碼：
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
using namespace std;
typedef long long ll;
/*
dp[i][j][k] :
i : 正在處理的數位
j : 支點的位置
k : 左右力矩之和(正負算，爲 0 就是平衡的)
dp[i][j][k]就是具備上述性質的數的個數
dp[i][j][k] = dp[i-1][j][ k + dig*(i-j)]
其中 dig 爲數位 i 處枚舉的可能的數字
狀態轉移中j沒有轉移？支點的位置須要另外枚舉
*/
ll dp[22][22][1600];//9*(1+2+3......+18) = 1539
int dig[22];//數字數位上的數字
ll dfs(int len,int p,int sum,bool up)//前3個參數對應dp3個維度的意義，up標記上界
{
if (len == 0) return sum==0;
if (sum < 0) return 0;
if (!up&&dp[len][p][sum]!=-1) return dp[len][p][sum];
ll ans = 0;
int n = 9;if (up) n = dig[len];
for (int i = 0;i <= n;++i)
{
ans += dfs(len-1,p,sum+i*(len-p),up&&(i==n));
}
if (!up) dp[len][p][sum] = ans;
return ans;
}
ll cal(ll x)
{
if (x == -1) return 0;//這題的 l 能夠爲 0,l-1就是-1了
int len = 0;
while (x)
{
dig[++len] = x%10;
x/=10;
}
//須要枚舉支點的位置
ll ans = 0;
for (int i = 1;i <= len;++i)
{
ans += dfs(len,i,0,1);
}
return ans - (len - 1);//減去重複的0
}
int main()
{
int T;mem(dp,-1);
scanf("%d",&T);
while (T--)
{
ll l,r;
scanf("%I64d %I64d",&l,&r);
printf("%I64d\n",cal(r)-cal(l-1));
}
return 0;
}
題意：
求區間[1,r]內數位含13且能夠整除13的數個數
分析：
含13的話類比第D題不要49，整除13類比F題整除7（都是一個調調）
直接類比D題和F題去作，這裏就很少說直接上代碼了：
PS：網上看了一下別人的題解，別人保存的狀態好像和個人有點差異
不過個人想法也很天然，反正本身看得蠻舒服的。。。。（主要是受前面D題F題的影響，天然而然的思想^_^）
#define mem(a,x) memset(a,x,sizeof(a))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<stdlib.h>
#include<cctype>
#include<string>
using namespace std;
typedef long long ll;
/*
dp[i][j][k][l]:
i : 正在處理的數位
j : %13 = j的數
k :這一位的前一位是否爲 1(是--1，否--0)
l :前面是否已經含 13(是--1，否--0)
*/
ll dp[22][13][2][2];
ll dig[22];
ll dfs(int len, int r,bool is1,bool has,bool up)
{
if (len == 0) return r == 0&&has;
if (!up&&dp[len][r][is1][has]!=-1) return dp[len][r][is1][has];
ll ans = 0;
int n = 9;if (up) n = dig[len];
for (int i = 0;i <= n;++i)
{
bool nhas = has;
if (is1&&i==3) nhas = 1;//已經有了13
ans += dfs(len-1,(i+r*10)%13,i==1,nhas,up&&(i==n));
}
if (!up) dp[len][r][is1][has] = ans;
return ans;
}
ll cal(ll x)
{
int len = 0;
while (x)
{
dig[++len] = x%10;
x/=10;
}
return dfs(len,0,0,0,1);
}
int main()
{
ll r;mem(dp,-1);
while (~scanf("%I64d",&r))
{
printf("%I64d\n",cal(r));
}
return 0;
}