5、数位DP

AcWing 338. 计数问题 (opens new window)

pos：当前遍历nums的位置 pre：之前位所有含1的个数 isLimit：是否挨着递增 leadZero：是否是前导0 先使用dfs暴力递归所有可能情况 在dfs中加入dp数组，相当于记忆性递归，空间换时间，Java代码如下 此模板适合其他所有数位DP题目 根据灵佬的Leetcode题目链接如下：

233. 数字 1 的个数 (opens new window)

面试题 17.06. 2出现的次数 (opens new window)

600. 不含连续1的非负整数 (opens new window)

2376. 统计特殊整数 (opens new window)

902. 最大为 N 的数字组合 (opens new window)

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();

        Scanner sc=new Scanner(System.in);
        int a=sc.nextInt();
        int b=sc.nextInt();
        while(!(a==0&&b==0)){
            if(a>b) {
                int temp=a;
                a=b;
                b=temp;
            }
            for (int i = 0; i < 10; i++) {
                main.flag=i;
                int l=main.solve(a-1);
                int r=main.solve(b);
                int res=r-l;
                System.out.print(res+" ");
            }
            System.out.println();
            a=sc.nextInt();
            b=sc.nextInt();
        }
    }

    char nums[];
    //dp[i][j]为当前在 i 位，前面有 j 个flag时的方案数。
    int dp[][];
    int len;
    int flag=0;
    int solve(long n) {
        nums = String.valueOf(n).toCharArray();
        len = nums.length;
        dp = new int[len][len];
        for (int[] item : dp) Arrays.fill(item, -1);
        return dfs(0, 0, true, true);
    }

    //当前位  前导0标记 位限制 前一位数
    //pre表示前面有几个flag
    int dfs(int pos, int pre, boolean isLimit, boolean leadZero) {
        if (pos >= len) return leadZero ? 0 : pre;
        if (!isLimit && !leadZero && dp[pos][pre] != -1) return dp[pos][pre];
        int res = 0;
        int up = isLimit ? nums[pos] - '0' : 9;
        for (int i = 0; i <= up; i++) {
            res += dfs(pos + 1, leadZero && i == 0 ? pre : i == flag ? pre+1  : pre,
                    isLimit && i == up, leadZero && i == 0);
        }
        //无限制，记忆化
        if (!isLimit && !leadZero) dp[pos][pre] = res;
        return res;
    }
}

笔记上写的

package javatest;

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        long startTime = System.currentTimeMillis();   //获取开始时间
        System.out.println(solution.solve(300000));
        long endTime = System.currentTimeMillis(); //获取结束时间
        System.out.println("dfs的时间： " + (endTime - startTime) + "ms");
    }

    char nums[];
    //dp[i][j]为当前在 i 位，前一位的数是 j 时的方案数。
    int dp[][];
    int len;

    int solve(long n) {
        nums = String.valueOf(n).toCharArray();
        len = nums.length;
        dp = new int[len][1<<10];
        for (int[] item : dp) Arrays.fill(item, -1);
        return dfs(0, 0, true, true);
    }

    //当前位  前导0标记 位限制 前一位数
    int dfs(int pos, int pre, boolean isLimit, boolean leadZero) {
        if (pos >= len) return leadZero ? 0 : 1;
        if (!isLimit && !leadZero && dp[pos][pre] != -1) return dp[pos][pre];
        int res = 0;
        int up = isLimit ? nums[pos] - '0' : 9;
        for (int i = 0; i <= up; i++) {
            //前导0（1位数全加） 或 相邻两数小于2
            if ((leadZero) || (pre >> i & 1) == 0)
                //有前导0标记并且当前遍历位为0，前导0传递下去
                //有限制标志并且当前遍历位到了最大值，传递限制
                //如果前导0且这一位也是0就按pre传递，否则再传新值
                //这种写法是忽略前导0的写法
                res += dfs(pos + 1, leadZero && i == 0 ? pre : pre | (1 << i),
                        isLimit && i == up, leadZero && i == 0);
        }
        //无限制，记忆化
        if (!isLimit && !leadZero) dp[pos][pre] = res;
        return res;
    }
}




/**
力扣233题，数位中寻找1的个数，模板
**/
package javatest;

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        long startTime = System.currentTimeMillis();   //获取开始时间
        System.out.println(solution.solve(123456789));
        long endTime = System.currentTimeMillis(); //获取结束时间
        System.out.println("dfs的时间： " + (endTime - startTime) + "ms");
    }

    char nums[];
    //dp[i][j]为当前在 i 位，前一位的数是 j 时的方案数。
    int dp[][];
    int len;

    int solve(long n) {
        nums = String.valueOf(n).toCharArray();
        len = nums.length;
        dp = new int[len][len];
        for (int[] item : dp) Arrays.fill(item, -1);
        return dfs(0, 0, true, true);
    }

    //当前位  前导0标记 位限制 前一位数
    int dfs(int pos, int pre, boolean isLimit, boolean leadZero) {
        if (pos >= len) {
            return leadZero ? 0 : pre;
        }
        if (!isLimit && !leadZero && dp[pos][pre] != -1) return dp[pos][pre];
        int res = 0;
        int up = isLimit ? nums[pos] - '0' : 9;
        for (int i = 0; i <= up; i++) {
            //前导0（1位数全加） 或 相邻两数小于2
            //if ((leadZero) || i == 1 || pre >= 0) {
            //等价于if(true)，写的时候脑子抽了
            if (true) {
                //有前导0标记并且当前遍历位为0，前导0传递下去
                //有限制标志并且当前遍历位到了最大值，传递限制
                //如果前导0且这一位也是0就按pre传递，否则再传新值
                //这种写法是忽略前导0的写法
                res += dfs(pos + 1, leadZero && i == 0 ? pre : i == 1 ? pre + 1 : pre,
                        isLimit && i == up, leadZero && i == 0);
            }
        }
        //无限制，记忆化
        if (!isLimit && !leadZero) dp[pos][pre] = res;
        return res;
    }
}