一開始刷dp就遇到了數位dp，以前程序設計藝術上看過一點，基本沒懂，于是趁今天遇到題目，想把它搞會，但就目前狀態來看仍然是似懂非懂啊，以后還要反復搞

統計區間[l,r]的滿足題意的數的個數，可以轉換成求[0,r]-[0,l)，這也是數位dp題的一個明顯的提示 F[i,st] 代表 位數為i（可能允許前導0。如00058也是個5位數），狀態為st的方案數。這里st根據題目需要確定。 如i=4,f[i,st]也就是0000~9999的符合條件的數的個數（十進制） 決策第i位是多少(such as 0~9)

這里采用的是記憶化搜索的處理方式，有模板

1 int dfs(int i, int s, bool e) { //i表示當前的位數，s表示狀態，e表示后面位數能否任意填 2 if (i==-1) return s==target_s; //最后一位取完，找到一個符合條件的值 3 if (!e && ~f[i][s]) return f[i][s]; //之前位數對應要求的值已經確定，在這里就直接返回 4 int res = 0; //記錄符合條件的值 5 int u = e?num[i]:9; //是否能任意填，能任意填則必須小于原來位數上對應的值，否則則可以去到0-9 6 for (int d = first?1:0; d <= u; ++d) //逐個填充值，通常會在下面繼續加上一些條件，排除不需要的值 7 res += dfs(i-1, new_s(s, d), e&&d==u); //下個位數 8 return e?res:f[i][s]=res; //可以任意填的話，說明到i位還未確定res沒有包含所有情況，不可以任意填說明后面已經確定，即f也可以確定 9 }

?2015-04-20 模板

1 int dfs(int p,int s,bool e) { 2 if(p==-1) return 1; 3 if(!e &&dp[p][s]!=-1) return dp[p][s]; 4 int res= 0; 5 int u=e?digit[p]:9; 6 for (int i=0;i<=u;++i) 7 { 8 if(i==4||(s&&i==2)) 9 continue ; 10 res+=dfs(p-1,i==6,e&&i==u); 11 } 12 return e?res:dp[p][s]=res; 13 } 14 int solve(int n) 15 { 16 int len=0; 17 while(n) 18 { 19 digit[len++]=n%10; 20 n/=10; 21 } 22 return dfs(len-1,0,1); 23 } View Code

?

正確與否有待進一步確認，第一遍看就暫且這么理解吧

f為記憶化數組；

i為當前處理串的第i位（權重表示法，也即后面剩下i+1位待填數）；

s為之前數字的狀態（如果要求后面的數滿足什么狀態，也可以再記一個目標狀態t之類，for的時候枚舉下t）；

e表示之前的數是否是上界的前綴（即后面的數能否任意填）。

for循環枚舉數字時，要注意是否能枚舉0，以及0對于狀態的影響，有的題目前導0和中間的0是等價的，但有的不是，對于后者可以在dfs時再加一個狀態變量z，表示前面是否全部是前導0，也可以看是否是首位，然后外面統計時候枚舉一下位數。

?

今天做了一道基礎數位dp題，來自hdu2089 題目大意：給定區間[n,m]，求在n到m中沒有“62“或“4“的數的個數。 如62315包含62，88914包含4，這兩個數都是不合法的。0<n<=m<1000000 那么就用這道題分析一下，首先放個源碼 1 #include <iostream> 2 using namespace std ; 3 int f[8][2] ;//f[i][0]:前i位符合要求 f[i][1]:前i位符合要求且i+1位是6 4 int digit[9] ;//digit[i]表示n從右到左第i位是多少 5 int dfs(int i,int s,bool e)//i表示當前位，s表示i位之前的狀態，e表示當前位是否可以隨意填寫 6 { 7 if(i==0) 8 return 1 ; 9 if(!e && f[i][s]!=-1) 10 return f[i][s] ; 11 int res=0 ; 12 int u=e?digit[i]:9 ; 13 for(int d=0 ;d<=u ;d++) 14 { 15 if(d==4 || (s && d==2)) 16 continue ; 17 res+=dfs(i-1,d==6,e&&d==u) ; 18 } 19 return e?res:f[i][s]=res ; 20 } 21 int callen(int n)//計算n的長度 22 { 23 int cnt=0 ; 24 while(n) 25 { 26 cnt++ ; 27 n/=10 ; 28 } 29 return cnt ; 30 } 31 void caldigit(int n,int len)//計算n的digit數組 32 { 33 memset(digit,0,sizeof(digit)) ; 34 for(int i=1 ;i<=len ;i++) 35 { 36 digit[i]=n%10 ; 37 n/=10 ; 38 } 39 } 40 int solve(int n)//計算[0,n]區間滿足條件的數字個數 41 { 42 int len=callen(n) ; 43 caldigit(n,len) ; 44 dfs(len,0,1) ; 45 } 46 int main() 47 { 48 int n,m ; 49 memset(f,-1,sizeof(f)) ; 50 while(~scanf("%d%d",&n,&m)) 51 { 52 if(n==0 && m==0) 53 break ; 54 printf("%d\n",solve(m)-solve(n-1)) ;//用[0,m]-[0,n)即可得到區間[n,m] 55 } 56 return 0 ; 57 }

2015-04-20 二次代碼，風格變好了很多

1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<queue> 7 #include<map> 8 using namespace std; 9 #define MOD 1000000007 10 const int INF=0x3f3f3f3f; 11 const double eps=1e-5; 12 #define cl(a) memset(a,0,sizeof(a)) 13 #define ts printf("*****\n"); 14 const int MAXN=1005; 15 int n,m,tt; 16 int digit[9],dp[8][2]; 17 int dfs(int p,int s,bool e) { 18 if(p==-1) return 1; 19 if(!e &&dp[p][s]!=-1) return dp[p][s]; 20 int res= 0; 21 int u=e?digit[p]:9; 22 for (int i=0;i<=u;++i) 23 { 24 if(i==4||(s&&i==2)) 25 continue ; 26 res+=dfs(p-1,i==6,e&&i==u); 27 } 28 return e?res:dp[p][s]=res; 29 } 30 int solve(int n) 31 { 32 int len=0; 33 while(n) 34 { 35 digit[len++]=n%10; 36 n/=10; 37 } 38 return dfs(len-1,0,1); 39 } 40 int main() 41 { 42 int i,j,k; 43 #ifndef ONLINE_JUDGE 44 freopen("1.in","r",stdin); 45 #endif 46 memset(dp,-1,sizeof(dp)); 47 while(scanf("%d%d",&n,&m)!=EOF) 48 { 49 if(n==0&&m==0) 50 break; 51 printf("%d\n",solve(m)-solve(n-1)); 52 } 53 } View Code

?

這里通過輸出中間變量來輔助理解

1 int dfs(int i,int s,bool e)//i表示當前位，s表示i位之前的狀態（這里表示是否為6），e表示當前位是否可以隨意填寫 2 { 3 //printf("*****\n"); 4 //printf("--%d %d %d\n",i,s,e); 5 if(i==0) 6 return 1 ; //說明前面的位數已經確定，該方案成立 7 if(!e && f[i][s]!=-1) 8 { 9 //printf("--%d %d %d\n",i,s,e); 10 return f[i][s] ; 11 } 12 13 int res=0 ; 14 int u=e?digit[i]:9 ; 15 //printf("--%d %d %d %d\n",i,s,e,u); 16 for(int d=0 ;d<=u ;d++) 17 { 18 if(d==4 || (s && d==2)) 19 continue ; 20 printf("--%d %d %d %d\n",i,s,e,d); 21 res+=dfs(i-1,d==6,e&&d==u) ; 22 } 23 printf("*************** %d %d %d %d\n",i,s,e,res); 24 return e?res:f[i][s]=res ; 25 }

這里輸出了0-200的情況

1 200
--3 0 1 0　　//從百位開始計算，之前沒有6，所以中間為0，后面可以任意填充所以為1，首先在第一位上填0
--2 0 0 0　　//第二位上填0
--1 0 0 0　　//第三位上填0，一種情況，res+1，下面一樣
--1 0 0 1　　//第三位上填1
--1 0 0 2
--1 0 0 3
--1 0 0 5
--1 0 0 6
--1 0 0 7
--1 0 0 8
--1 0 0 9　　//第三位上填9
***************? 1 0 0 9　　//f[1][0]=9，個位上的情況且十位不含6全部確定共9種,下一步之前res重新清零
--2 0 0 1　　//十位填2，之后再確定個位，發現個位上的情況已經確定，于是直接返回f[1][0],res+f[1][0]
--2 0 0 2
--2 0 0 3
--2 0 0 5
--2 0 0 6　　//十位填6，之后s變為1，個位需要重新確定
--1 1 0 0
--1 1 0 1
--1 1 0 3
--1 1 0 5
--1 1 0 6
--1 1 0 7
--1 1 0 8
--1 1 0 9
***************? 1 1 0 8　　f[1][1]=8? //個位上十位含6共9種情況
--2 0 0 7　　//繼續枚舉十位
--2 0 0 8
--2 0 0 9
***************? 2 0 0 80?? //f[2][0]=80
--3 0 1 1　　//百位填1? ret+f[2][0]
--3 0 1 2　　//百位填2? ret+f[2][0]
--2 0 1 0　　//十位填0
--1 0 1 0　　//個位填0? ret+1
***************? 1 0 1 1　　//個位上只能有0
***************? 2 0 1 1　　//十位上只能有00
***************? 3 0 1 161? //返回的是ret
161

正確性有待商榷，待我再多做幾道題看看

更多數位dp題可以參見我博客，代碼風格基本是統一的

?

?

?

?

?

轉載于:https://www.cnblogs.com/cnblogs321114287/p/4260821.html

總結

以上是生活随笔為你收集整理的初探数位DP-hdu2089的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。