前言

今天淺談一下數(shù)位dp的板子，我最初接觸到數(shù)位dp的時候，感覺數(shù)位dp老難了，一直不敢寫，最近重新看了一些數(shù)位dp，發(fā)現(xiàn)沒有想象中那么難，把板子搞會了，變通也會變的靈活的多！

引入

以一道例題作為數(shù)位dp的引入，題目如下，鏈接

數(shù)據(jù)范圍為1e9，一般的算法很難把這道題拿下，類似求在一段區(qū)間范圍內(nèi)，滿足某些條件的數(shù)字的個數(shù)，并且數(shù)據(jù)范圍很大時就會聯(lián)想到數(shù)位dp算法。

第一個板子

我遇到的數(shù)位dp板子有三個，第一個來源于y總的講解，附上鏈接和這道題的代碼，y總的講解邏輯清晰，想學(xué)習(xí)可以直接看視頻。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.Scanner;public class Main {static int[][] f = new int[11][10];static int k;
public static void main(String[] args) throws IOException {StreamTokenizer sc=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));sc.nextToken();//Scanner scanner = new Scanner(System.in);int t = (int)sc.nval;while(t> 0) {t--;sc.nextToken();k = (int)sc.nval;sc.nextToken();int l = (int)sc.nval;sc.nextToken();int r = (int)sc.nval;//int l = scanner.nextInt();//int r = scanner.nextInt();for (int i = 0; i < 11; i++) {Arrays.fill(f[i], 0);}init();System.out.println(dp(r) - dp(l - 1));//dp(r);}return;
}private static int dp(int num) {// TODO Auto-generated method stubif(num == 0) {return 0;}int res = 0;int last = 0;//上一個位數(shù)的數(shù)字int[] nu = new int[12];int n = 1;while (num > 0 ) {nu[n++] = num%10;num = num / 10;}n--;//System.out.println(n);for (int i = n; i > 0; i--) {//遍歷位數(shù)int x = nu[i];int jj;if(i == n) {jj = 1;}else {jj = 0;}//System.out.println(x);//System.out.println(last);for (; jj < x; jj++) {//遍歷該位數(shù)上可以填的數(shù)字if(Math.abs(jj - last) <= k || i == n) {//System.out.println("mm" + i);res += f[i][jj];}}if(Math.abs(x-last) <= k || i == n) {last = x;//System.out.println("1111");}else {break;}if(i==1) {res++;}}//加包含前導(dǎo)0的，其實(shí)就是加上不是和num同位數(shù)的數(shù)字，for (int i = 1; i < n; i++) {for (int j = 1; j < 10; j++) {//從1開始res += f[i][j];}}//System.out.println(res);return res;
}private static void init() {// TODO Auto-generated method stubfor (int i = 0; i < 10; i++) {//初始化只有一位數(shù)字的時候，一定符合要求f[1][i] = 1;//注意i一定從0開始}for (int i = 2; i < 10; i++) {//初始化其它位數(shù)的數(shù)字for (int j = 0; j < 10; j++) {//注意，這里可以包含0for (int m = 0; m < 10; m++) {if(Math.abs(m-j) <= k) {f[i][j] += f[i-1][m];}}}}
}
}

第二個板子

1. 求區(qū)間[L,R]內(nèi)符合條件的數(shù)字，轉(zhuǎn)換為求區(qū)間[0,L-1]與[0,R]內(nèi)符合條件的數(shù)字個數(shù)，答案就是這兩個做差。
2. 在遍歷數(shù)字的時候，先遍歷數(shù)字的位數(shù)，假設(shè)我要求[0,R]內(nèi)滿足條件的數(shù)字，R的位數(shù)為cnt，在遍歷cnt的時候我要注意，不能超過R，如果R是23456，那么第cnt位能夠選擇的數(shù)字范圍是[0,2]。如果我第cnt位選擇了1，在遍歷cnt-1位的時候我就不需要考慮遍歷數(shù)字是否越界問題，因?yàn)閏nt位已經(jīng)決定了后面的位數(shù)怎么選都不會比23456大。如果第cnt位選擇了2，在遍歷cnt-1位時我可以填的范圍就變成了[0,3]，所以我需要有一個變量記錄當(dāng)前我前面選擇的數(shù)字是否是貼上界的，令這個變量為limit，如果limit=1，當(dāng)前位數(shù)可以選擇的數(shù)字上界是a[cnt]，否則就是9，其中數(shù)組a是把23456拆分的結(jié)果，拆分代碼如下

int cnt = 0;while(n > 0) {a[++cnt] = (int) (n%10);n/=10;}

根據(jù)上述分析，會有如下代碼，

int up = limit==1?a[cnt]:9;//求當(dāng)前位數(shù)最大能夠填的數(shù)字
limit&(i==up?1:0)//下一個limit是否還等于1，i表示當(dāng)前位數(shù)填的數(shù)字，如果填了最大的那個數(shù)，且當(dāng)前的limit是1，則填下一位數(shù)時能夠填的最大數(shù)字也是受約束的

up表示當(dāng)前位數(shù)可以填的數(shù)字上界。

3. 接下來處理一下前導(dǎo)零，如果前導(dǎo)零的存在不會影響結(jié)果，那么不需要處理，否則就要處理一下前導(dǎo)零。比如求包含2和4的數(shù)字個數(shù)就不需要處理前導(dǎo)0，因?yàn)樗挥绊懡Y(jié)果。如果要求數(shù)字各個位數(shù)不為0
   假設(shè)我要求[0,R]內(nèi)滿足條件的數(shù)字，R的位數(shù)為cnt，在遍歷cnt的時候我要注意，在這個位置填的0就是前導(dǎo)0，如果我在這個位置填了0，再去遍歷第cnt-1位數(shù)字時，這里填的0還是前導(dǎo)0.如果我第cnt位沒有填0，那么我在cnt-1位填的0就不是前導(dǎo)0，他是有效的一維數(shù)，就像001和101一樣，00里面的0都是前導(dǎo)0，是無效的。而10里的0是十位上的0，是有效的。我們用zeros來表示當(dāng)前位的0是否是前導(dǎo)0，第cnt位的0肯定是前導(dǎo)0，如果第cnt位填了0，第cnt-1位的0才是前導(dǎo)0，否則就不是。所以有

   zeros&(i==0?1:0)//表示下一位的zeros是否是0，i表示當(dāng)前位填的數(shù)字，如果當(dāng)前位填了0并且當(dāng)前位的zeros是1，那么下一位的zeros也是1.

   前導(dǎo)0的使用要比上界limit的使用更靈活一點(diǎn)，他是根據(jù)題目的要求來使用的。

4. 這里主要講記憶化遞歸。因?yàn)檫@一個板子用的是dfs，而dfs可能會有超時的問題，所以就有了記憶化遞歸。記憶化遞歸要標(biāo)記好當(dāng)前的狀態(tài)，所以用來記憶當(dāng)前狀態(tài)的數(shù)組也是要根據(jù)題目設(shè)定。
   當(dāng)題目中有多個測評樣例時，進(jìn)行記憶化的時候要注意不要記住在特定數(shù)下的答案。所以有下面的代碼

   if(limit == 0) dp[cnt][last][zeros] = res;

   為什么要在limit=0時才進(jìn)行記憶化呢？因?yàn)閘imit=1說明當(dāng)前的數(shù)是貼上界的，而這個數(shù)是受當(dāng)前這個樣例影響的，比如2345這個數(shù)字，在遍歷到百位數(shù)字3時，我是貼上界的，如果千位數(shù)字是2，那么此時十位數(shù)字只能選0-4，此時得到的res是從0-4遞歸得到的。但是如果換一個數(shù)字2377，在遍歷到百位數(shù)字3時，我如果是不貼上界的，可選的數(shù)字應(yīng)該是0-9，如果是貼上界的，可選的數(shù)字是0-7，明顯此時的狀態(tài)dp[3][3][0]和數(shù)字2345的轉(zhuǎn)移是不一樣的。所以我只有不貼上界的時候，說明后面的轉(zhuǎn)移都是0-9時才進(jìn)行記憶。
   讀取記憶的時候也是同樣的道理，

   if(limit==0&&dp[cnt][last][zeros]!=-1) { return dp[cnt][last][zeros]; }

   只有此時不貼上界的時候才能讀取之前的記憶。
   記憶化數(shù)組根據(jù)具體的題目來設(shè)定，并不是統(tǒng)一的，具有高度靈活性，只要解釋起來沒問題就可以。像小明數(shù)這道題沒有記憶limit，有些情況也是可以記憶limit的。

分析題目

針對小明數(shù)而言，前導(dǎo)0會影響答案，為什么？題目要求相鄰兩數(shù)之差絕對值不超過k，如果存在前導(dǎo)0并且不加以判斷那么會認(rèn)為前導(dǎo)0也是有效數(shù)字，那么0后面只能填0-k，但實(shí)際前導(dǎo)0應(yīng)該是無效數(shù)字，前面一個數(shù)字是前導(dǎo)0，后面可以填0~9中的任意一個數(shù)字。如果沒有判斷前導(dǎo)零，會導(dǎo)致結(jié)果比實(shí)際的小。 求某些數(shù)字相鄰位數(shù)上的數(shù)字之差的絕對值不超過k，來想一下dfs的時候需要什么，必然要有的是當(dāng)前的位數(shù)cnt和是否貼上界limit，剛剛也分析了需要判斷前導(dǎo)零，所以有zeros。遍歷到cnt位時，來判斷一下當(dāng)前位可以填啥，我要滿足相鄰位數(shù)上的數(shù)字之差的絕對值不超過k，我得知道前一個位數(shù)我填的是幾，所以就有了last，指示前一個位數(shù)上填的數(shù)字。然后就沒有其它的了，所以 dfs(cnt,last,zeros,limit)，接下來就直接放代碼了。

import java.util.Arrays;
import java.util.Scanner;
public class Main {static int dp[][][] = new int[20][20][2];//還要記錄當(dāng)前的狀態(tài)是不是有前導(dǎo)零！！！！！！！static int a[] = new int[20];static int k,ans;static int nums[] = new int[20];
public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int t = scanner.nextInt();while(t-- > 0) {for(int i = 0;i < 20;i++)for(int j = 0;j < 20;j++)Arrays.fill(dp[i][j],-1);k = scanner.nextInt();long l = scanner.nextLong();long r = scanner.nextLong();System.out.println(solve(r)-solve(l-1));private static int solve(long n) {// TODO Auto-generated method stubint cnt = 0;while(n > 0) {a[++cnt] = (int) (n%10);n/=10;}return dfs(cnt,1,-1,1);
}private static int dfs(int cnt, int limit, int last,int zeros) {//前導(dǎo)0對答案有影響！！！！！！// TODO Auto-generated method stubif(cnt==0) {return 1;}if(limit==0&&dp[cnt][last][zeros]!=-1) {return dp[cnt][last][zeros];}int res =0;int up = limit==1?a[cnt]:9;for(int i = 0;i <= up;i++) {if(Math.abs(last-i)<=k||zeros==1) {//3 1 2 0 dp[1][0]nums[cnt] = i;res += dfs(cnt-1, limit&(i==up?1:0), i,zeros&(i==0?1:0));//120}}if(limit == 0) dp[cnt][last][zeros] = res;	     return res;
}
}

如果代碼有問題，歡迎在評論區(qū)內(nèi)提出來！第三個板子就不講啦，其實(shí)就是把第二個板子的dfs變成dp，但是個人感覺沒有dfs靈活，目前在用第二個板子。