什么网站上做推广效果比较好,wordpress插件的开发,搜索自媒体平台,wordpress.html前言
今天浅谈一下数位dp的板子#xff0c;我最初接触到数位dp的时候#xff0c;感觉数位dp老难了#xff0c;一直不敢写#xff0c;最近重新看了一些数位dp#xff0c;发现没有想象中那么难#xff0c;把板子搞会了#xff0c;变通也会变的灵活的多#xff01;
引入…前言
今天浅谈一下数位dp的板子我最初接触到数位dp的时候感觉数位dp老难了一直不敢写最近重新看了一些数位dp发现没有想象中那么难把板子搞会了变通也会变的灵活的多
引入
以一道例题作为数位dp的引入题目如下链接 数据范围为1e9一般的算法很难把这道题拿下类似求在一段区间范围内满足某些条件的数字的个数并且数据范围很大时就会联想到数位dp算法。
第一个板子
我遇到的数位dp板子有三个第一个来源于y总的讲解附上链接和这道题的代码y总的讲解逻辑清晰想学习可以直接看视频。
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 scnew 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;//上一个位数的数字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--) {//遍历位数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) {//遍历该位数上可以填的数字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(i1) {res;}}//加包含前导0的其实就是加上不是和num同位数的数字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) {//初始化只有一位数字的时候一定符合要求f[1][i] 1;//注意i一定从0开始}for (int i 2; i 10; i) {//初始化其它位数的数字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];}}}}
}
}第二个板子
求区间[L,R]内符合条件的数字转换为求区间[0,L-1]与[0,R]内符合条件的数字个数答案就是这两个做差。在遍历数字的时候先遍历数字的位数假设我要求[0,R]内满足条件的数字R的位数为cnt在遍历cnt的时候我要注意不能超过R如果R是23456那么第cnt位能够选择的数字范围是[0,2]。如果我第cnt位选择了1在遍历cnt-1位的时候我就不需要考虑遍历数字是否越界问题因为cnt位已经决定了后面的位数怎么选都不会比23456大。如果第cnt位选择了2在遍历cnt-1位时我可以填的范围就变成了[0,3]所以我需要有一个变量记录当前我前面选择的数字是否是贴上界的令这个变量为limit如果limit1当前位数可以选择的数字上界是a[cnt]否则就是9其中数组a是把23456拆分的结果拆分代码如下
int cnt 0;while(n 0) {a[cnt] (int) (n%10);n/10;}根据上述分析会有如下代码
int up limit1?a[cnt]:9;//求当前位数最大能够填的数字
limit(iup?1:0)//下一个limit是否还等于1i表示当前位数填的数字如果填了最大的那个数且当前的limit是1则填下一位数时能够填的最大数字也是受约束的up表示当前位数可以填的数字上界。 接下来处理一下前导零如果前导零的存在不会影响结果那么不需要处理否则就要处理一下前导零。比如求包含2和4的数字个数就不需要处理前导0因为他不影响结果。如果要求数字各个位数不为0 假设我要求[0,R]内满足条件的数字R的位数为cnt在遍历cnt的时候我要注意在这个位置填的0就是前导0如果我在这个位置填了0再去遍历第cnt-1位数字时这里填的0还是前导0.如果我第cnt位没有填0那么我在cnt-1位填的0就不是前导0他是有效的一维数就像001和101一样00里面的0都是前导0是无效的。而10里的0是十位上的0是有效的。我们用zeros来表示当前位的0是否是前导0第cnt位的0肯定是前导0如果第cnt位填了0第cnt-1位的0才是前导0否则就不是。所以有 zeros(i0?1:0)//表示下一位的zeros是否是0i表示当前位填的数字如果当前位填了0并且当前位的zeros是1那么下一位的zeros也是1. 前导0的使用要比上界limit的使用更灵活一点他是根据题目的要求来使用的。 这里主要讲记忆化递归。因为这一个板子用的是dfs而dfs可能会有超时的问题所以就有了记忆化递归。记忆化递归要标记好当前的状态所以用来记忆当前状态的数组也是要根据题目设定。 当题目中有多个测评样例时进行记忆化的时候要注意不要记住在特定数下的答案。所以有下面的代码 if(limit 0) dp[cnt][last][zeros] res; 为什么要在limit0时才进行记忆化呢因为limit1说明当前的数是贴上界的而这个数是受当前这个样例影响的比如2345这个数字在遍历到百位数字3时我是贴上界的如果千位数字是2那么此时十位数字只能选0-4此时得到的res是从0-4递归得到的。但是如果换一个数字2377在遍历到百位数字3时我如果是不贴上界的可选的数字应该是0-9如果是贴上界的可选的数字是0-7明显此时的状态dp[3][3][0]和数字2345的转移是不一样的。所以我只有不贴上界的时候说明后面的转移都是0-9时才进行记忆。 读取记忆的时候也是同样的道理 if(limit0dp[cnt][last][zeros]!-1) { return dp[cnt][last][zeros]; } 只有此时不贴上界的时候才能读取之前的记忆。 记忆化数组根据具体的题目来设定并不是统一的具有高度灵活性只要解释起来没问题就可以。像小明数这道题没有记忆limit有些情况也是可以记忆limit的。
分析题目
针对小明数而言前导0会影响答案为什么题目要求相邻两数之差绝对值不超过k如果存在前导0并且不加以判断那么会认为前导0也是有效数字那么0后面只能填0-k但实际前导0应该是无效数字前面一个数字是前导0后面可以填0~9中的任意一个数字。如果没有判断前导零会导致结果比实际的小。 求某些数字相邻位数上的数字之差的绝对值不超过k来想一下dfs的时候需要什么必然要有的是当前的位数cnt和是否贴上界limit刚刚也分析了需要判断前导零所以有zeros。遍历到cnt位时来判断一下当前位可以填啥我要满足相邻位数上的数字之差的绝对值不超过k我得知道前一个位数我填的是几所以就有了last指示前一个位数上填的数字。然后就没有其它的了所以 dfs(cnt,last,zeros,limit)接下来就直接放代码了。
import java.util.Arrays;
import java.util.Scanner;
public class Main {static int dp[][][] new int[20][20][2];//还要记录当前的状态是不是有前导零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) {//前导0对答案有影响// TODO Auto-generated method stubif(cnt0) {return 1;}if(limit0dp[cnt][last][zeros]!-1) {return dp[cnt][last][zeros];}int res 0;int up limit1?a[cnt]:9;for(int i 0;i up;i) {if(Math.abs(last-i)k||zeros1) {//3 1 2 0 dp[1][0]nums[cnt] i;res dfs(cnt-1, limit(iup?1:0), i,zeros(i0?1:0));//120}}if(limit 0) dp[cnt][last][zeros] res; return res;
}
}
如果代码有问题欢迎在评论区内提出来第三个板子就不讲啦其实就是把第二个板子的dfs变成dp但是个人感觉没有dfs灵活目前在用第二个板子。
