首页 > 代码库 > 数位DP小结

数位DP小结

数位DP,本质上来说还是DP。只不过DP的定义和数字的每一位有关。

这里简单的讲解两道题的思路,抛砖迎玉,作为数位DP的入门。

 

第一题,http://acm.hdu.edu.cn/showproblem.php?pid=2089    不要62和4

题目大意:不吉利的数字为所有含有4或62的号码。例如:
62315 73418 88914
都属于不吉利号码。但是,61152虽然含有6和2,但不是62连号,所以不属于不吉利数字之列。
你的任务是,对于每次给出的一个牌照区间号,推断出交管局今次又要实际上给多少辆新的士车上牌照了。

Input
输入的都是整数对n、m(0<n≤m<1000000),如果遇到都是0的整数对,则输入结束。
Output
对于每个整数对,输出一个不含有不吉利数字的统计个数,该数值占一行位置。
 
思路:没有接触数位DP的时候,最原始的思路是遍历区间[n, m]之间的所有数字,对每个数字进行判断,统计符合条件的数的个数。显然这个原始的暴力枚举思路,时间复杂度是不能AC的。
         而这个时间复杂度已经是O(m-n)的思路都不能AC,时间复杂度比一次线性还小的,只有二分法和DP的方法了。这个题和二分法没有关系,那么就只能考虑空间换时间的DP了。
  因为我们发现,数的条件是对每个数位上的数进行限制,就是数位DP。
  定义,DP[i][j], 数的长度为i,最高位数字为j,满足条件的数有多少个。
  转移方程DP[i][j]=  if j==4 : DP[i][j]=0   
            elif j ==6 : DP[i][j] = ∑DP[i-1][k]   (k=0,1,3,4,5,6,7,8,9)
            elif j != 6  :  DP[i][j] = ∑DP[i-1][k]   (k=0,1,2,3,4,5,6,7,8,9)
        这个转移方程就是有题意得来的,不能有4,所以j==4的时候,显然没有满足条件的数。
                       当j==6的时候,也就是最高为是6,那么次高位就不能为2了,所以求和的时候k没有取2
                        剩余情况就是所有次高位不限了。当然这里可以不取4,即使取4也没关系,因为DP[i][j]的i是从小到大计算的,次高位为4,DP[][4]=0
 
  初始化,dp[0][0] = 1.
  
  获得这个DP数组之后,我们可以根据这个数组计算,(0,x)之间的数,有多少符合条件的数,那么,定义一个help(x)函数即可。
     结果   help(n+1) - help(m)
 
代码如下:
技术分享
import java.util.Scanner;


public class Main {

    public static int[][] dp;

    public static void main(String[] args) {
        dp = new int[7][10];
        getdp();
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        while (!(m == 0 && n == 0)) {
            System.out.println(helper(n + 1) - helper(m));
            m = in.nextInt();
            n = in.nextInt();
        }
        in.close();
        return;
    }

    public static void getdp() {
        dp[0][0] = 1;
        for (int i = 1; i < 7; i++) {
            for (int j = 0; j < 10; j++) {
                if (j == 4) {
                    dp[i][j] = 0;
                } else if (j == 6) {
                    for (int k = 0; k < 10; k ++) {
                        dp[i][j] += dp[i - 1][k]; 
                    }
                    dp[i][j] -= dp[i - 1][2];
                } else {
                    for (int k = 0; k < 10; k ++) {
                        dp[i][j] += dp[i - 1][k]; 
                    }
                }
            }
        }
    }
    public static int helper(int x) {
        int[] a = new int[8];
        a[0] = 0;//a[0] 用来存储index
        while (x > 0) {
            a[++a[0]] = x % 10;
            x /= 10;
        }
        a[7] = 0;  //车牌一共6位,a[7]补0,为了后面写法方便
        int res = 0;
        for (int i = a[0]; i >= 1; i--) {
            for (int j = 0; i < a[i]; j++) {
                if (j != 4 && !(a[i + 1] == 6 && j == 2)) {
                    res += dp[i][j];
                }
            }
            if (a[i] == 4) {
                break;
            }
            if (a[i + 1] == 6 && a[i] == 2) {
                break;
            }
        }
        return res;
    }
}
no 62 and 4

 

 

 

 

第二题。http://hihocoder.com/problemset/problem/1520?sid=1111176

描述

小Hi有一张纸条,上面写着一个长度为N的整数。由于年代过于久远,其中有些位置已经看不清了,我们用‘?‘来代替这个位置。小Hi印象中记得这个数字除以X的余数为Y,他想知道这个数最小可能是多少?

注意这个整数的首位不能是0,除非它本身等于0。

输入

第1行:1个长度为N的字符串,只包含数字0~9和‘?‘,1≤N≤200

第2行:两个整数,X和Y,1≤X≤200,000,0≤Y<X

输出

第1行:若存在解,则输出最小可能的数字,否则输出No solution

 

 

思路: 和上一题类似,暴力枚举是显然不行的,这里的数最高长达200位,2^200次方的枚举量,显然是不能AC的。

  这个题和余数有关,所以思考建立数组,保存余数相关信息,进行dp。最简单的就是进行记忆化搜索,在暴力枚举的同时,记录枚举到当前位的已知余数是多少,如果已经遍历过,则可以直接跳过,这样可以节省许多计算量。

  定义,dp[i][j] 表示,从最高位开始遍历的第i位的时候,余数是j的情况,是否遍历过。(遍历过则说明,第i位之后的所有位,不管取任何值都不会有满足题意的解,否则已经退出枚举直接输出结果了。)

  没有转移方程。

  初始化所有dp都是 false

  

举例说明思路,例如输入时1??00??00

如果第1个问号取0,第二个问号也取0,后两个问号,无论如何都不能取到满足条件的解。那么dp[3][j]=true;

下一次,再到第3位的时候,如果此时前三位计算得到的余数还是j电话,那么就不用再计算后面的几位的,因为无论取什么值,也不会有满足余数条件的解。这样就可以直接第三位取下一个值来判断了。

 

(这个题还用到了一些其他的方法来减少计算量,比如,预先计算一个数组expRem[i],用来保存10^i % X的余数。其实就是利用了mod运算的一些性质,来简化运算。) 

 

 

代码如下:

技术分享
import java.util.Scanner;
//import java.util.*;

public class  Main {
    public static StringBuilder numbers;
    public static boolean[][] dp;
    public static int[] expRem;
    public static int X;
    public static int Y;
    public static int N;
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        numbers = new StringBuilder(in.nextLine());
        X = in.nextInt();
        Y = in.nextInt();
        N = numbers.length();
        in.close();
        
        dp = new boolean[N][X];
        expRem = new int[N];
        
        boolean exist_unknow = false;
        for (int i = 0; i < N; i++) {
            if (numbers.charAt(i) == ‘?‘) {
                exist_unknow = true;
                break;
            }
        }
        expRem[N - 1] = 1;
        for(int i = N - 2; i >= 0;i--){
            expRem[i] = expRem[i + 1] * 10 % X;
        }
        //System.out.print(exist_unknow);
        
        if (!exist_unknow) {
            for(int i = 0; i < N; i++)
            {
                Y=(Y - expRem[i] * (numbers.charAt(i) -‘0‘) % X + X )% X;
            }
            if(Y==0)
            {
                System.out.print(numbers);
            }else {
                System.out.print("No solution");
            }
            return;
        }
        if(N == 1)
        {
            for(int i = 0; i < 10; i++)
            {
                if(i % X == Y)
                {
                    System.out.print(i);
                    return;
                }
            }
            System.out.print("No solution");
            return;
        }
        if(dfs(0,Y)){

        }else {
            System.out.print("No solution");
        }
        return;
    }
    public static boolean dfs(int depth, int target) {
        if (depth == N) {
            if (target == 0) {
                System.out.print(numbers);
                return true;
            } else {
                return false;
            }
        }
        if (dp[depth][target]) {
            return dp[depth][target];
        }
        if (numbers.charAt(depth) != ‘?‘) {
            int newTarget = (target - expRem[depth] * (numbers.charAt(depth) - ‘0‘) % X + X) % X;
            dp[depth][target] = dfs(depth + 1, newTarget);
            return dp[depth][target];
        }
        dp[depth][target] = false;
        int index = 0;
        if (depth == 0) {
            index = 1;
        }
        for (; index <= 9; index++) {
            char newChar = (char) (‘0‘ + index);
            numbers.setCharAt(depth, newChar);
            
            int newTarget = (target - expRem[depth] * (numbers.charAt(depth) - ‘0‘) % X + X) % X;
            if (dfs(depth + 1, newTarget)) {
                dp[depth][target] = true;
                return dp[depth][target];
            }
        }
        numbers.setCharAt(depth, ‘?‘);
        return dp[depth][target];
    }
}
古老数字

 

数位DP小结