欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【算法笔记】数位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 ] ,让你求这个区间中满足 某种条件 的数的总数。而条件一般与数的大小无关,而与数的组成有关。

例题:P2657 [SCOI2009] windy 数

题目概述: 不含前导零且相邻两个数字之差至少为 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