【算法笔记】数位DP入门
程序员文章站
2022-05-18 17:50:33
给定一个闭区间 [ A, B ] ,让你求这个区间中满足 某种条件 的数的总数。而条件一般与数的大小无关,而与数的组成有关。例题:P2657 [SCOI2009] windy 数题目概述: 不含前导零且相邻两个数字之差至少为 22 的正整数被称为 windy 数。windy 想知道,在 aa 和 bb 之间,包括 aa 和 bb ,总共有多少个 windy 数?题意解析: 如 13,13,1,2,3,4等数字均为windy数,因为相邻两个数字之间的差大于等于2,反之10, 11, 12则不是。....
给定一个闭区间 [ A, B ] ,让你求这个区间中满足 某种条件 的数的总数。而条件一般与数的大小无关,而与数的组成有关。
题目概述: 不含前导零且相邻两个数字之差至少为 22 的正整数被称为 windy 数。windy 想知道,在 aa 和 bb 之间,包括 aa 和 bb ,总共有多少个 windy 数?
题意解析: 如 13,13,1,2,3,4等数字均为windy数,因为相邻两个数字之间的差大于等于2,反之10, 11, 12则不是。
解题思路:
对于求区间 [ A, B ] ,可以转换成求区间 [ 1, A-1 ] 和 [ 1, B ]
ans (A, B) = ans(1, B) - ans(1, A-1) 这样一来就只需要考虑上边界即可。
举例,考虑 [ 1, 12345 ] 区间之间的windy数的数量。
将数字顺序转化为字典序, 所有长度小于5数都补上前导零, 1 -> 00001 , 12 -> 00012。
利用DFS从最高位到最低位枚举。
记录状态:
1、当前枚举到了哪一位
2、 前面一位数是多少
3、 当前位可以填入哪些数字
- 如果前面一位数是0,则当前位可以取0-9。
- 如果之前所有数都等于区间上限,那么当前数字可选范围应当小于等于区间上限的当前位,如前几位数是123,则当前只能取0-4,取5的话就成了1235,超出了上限。
核心代码:
// index 当前位置索引; st 表示状态,即前一位数是多少; op 表示与区间上限的大小关系(当前能取哪些数)
int dfs(int index, int st, boolean op){
int result = 0; // 统计结果
if(index > this.len-1) return 1; // 搜索结束
int maxNum = op ? upper_bound[index] : 9; // 当前能够取到的最大值,此处 upper_bound[] = {1,2,3,4,5}
for(int i=0; i<=maxNum; i++){ // 开始递归
if(Math.abs(st-i)<2){
continue;
}
if( st==11 && i==0 ){ // st == 11表示前导数是0的情况,下一个值的取值范围0-9
result += dfs(index+1, 11, op && i==upper_bound[index]);
}
else{
result += dfs(index+1, i, op && i==upper_bound[index]);
}
}
return result;
通过上述代码可以发现,如果op为false,不考虑op,当前递归结果都是相同的,和op没有关系。
因此可以将该状态记录下来,这就是数位dp的思想所在。
优化之后的代码:
int dfs(int index, int st, boolean op){
int result = 0;
if(index>this.len-1) return 1;
if(!op&&dp[index][st]!=-1) return dp[index][st]; // 新加代码 与之前数组的不同在于,添加了dp数组记录状态
int maxNum = op ? upper_bound[index] : 9;
for(int i=0; i<=maxNum; i++){
if(Math.abs(st-i)<2){
continue;
}
if( st==11 && i==0 ){
result += dfs(index+1, 11, op && i==maxNum);
}
else{
result += dfs(index+1, i, op && i==maxNum);
}
}
if(!op) dp[index][st] = result; // 新加代码
return result;
完整Java代码:
import java.util.Scanner;
public class Main {
public static void main(String [] args){
Scanner in = new Scanner(System.in);
int a = in.nextInt()-1, b = in.nextInt();
windyNumber A = new windyNumber(a+"");
windyNumber B = new windyNumber(b+"");
System.out.println(B.getCount()-A.getCount());
}
}
class windyNumber{
int len;
int[] upper_bound;
int[][] dp = new int[15][15];
windyNumber(String a){
this.len = a.length();
upper_bound = new int[len];
for(int i=0; i<len; i++){
upper_bound[i] = a.charAt(i) - '0';
}
for (int i=0; i<15; i++)
for (int j=0; j<15; j++)
dp[i][j] = -1;
}
int getCount(){
return dfs(0, 11, true);
}
int dfs(int index, int st, boolean op){
int result = 0;
if(index>this.len-1) return 1;
if(!op&&dp[index][st]!=-1) return dp[index][st];
int maxNum = op ? upper_bound[index] : 9;
for(int i=0; i<=maxNum; i++){
if(Math.abs(st-i)<2){
continue;
}
if( st==11 && i==0 ){
result += dfs(index+1, 11, op && i==maxNum);
}
else{
result += dfs(index+1, i, op && i==maxNum);
}
}
if(!op) dp[index][st] = result;
return result;
}
}
本文地址:https://blog.csdn.net/qq_45271256/article/details/107340815
上一篇: aix 部分命令
下一篇: 什么是对象的浅度克隆和深度克隆?