数位dp模板（windy数）

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;
    }
}