【剑指offer】整数中1出现的次数

// 入门数位DP
我就说肯定能用一维DP数组求解，结果连续WA了两天，最后对数逐位分析发现，java代码中全局变量没有赋到值...
由于本题是入门性数位DP，状态是用一维存储，故大多数题解是线性递推求解的。

【拓展】

1. 数位DP的复杂度为O（状态数*转移数） //状态数是dp数组的大小，转移数是for循环大小
2. 数位dp总结之从入门到模板 https://blog.csdn.net/wust_zzwh/article/details/52100392

import java.util.Arrays;
import java.util.Scanner;

public class Solution {

    static int[] a = new int[10];
    static int[] dp = new int[10];
    static int[] pow = new int[10];
    static int N;

    public static int dfs(int pos, boolean limit) {
        if (pos == -1) {
            return 0;
        }
        if (!limit && dp[pos] != -1) {
            return dp[pos];
        }

        int up = limit ? a[pos] : 9;
        int ans = 0;
        for (int i = 0; i <= up; i++) {
            if (i == 1) {
                if (limit && i == a[pos]) {
                    ans += N % pow[pos] + 1;
                } else {
                    ans += pow[pos];
                }
            }
            int flag = dfs(pos - 1, limit && i == a[pos]);
            ans += flag;
        }
        if (!limit) {
            dp[pos] = ans;
        }
        return ans;

    }

    public static int NumberOf1Between1AndN_Solution(int n) {

        int pos = 0;
        N = n;
        while (n > 0) {
            a[pos++] = n % 10;
            n /= 10;
        }
        Arrays.fill(dp, -1);
        pow[0] = 1;
        for (int i = 1; i < pow.length; i++) {
            pow[i] = pow[i - 1] * 10;
        }
        return dfs(pos - 1, true);
    }

    public static void main(String[] args) {
        while (true) {
            int n = new Scanner(System.in).nextInt();
            System.out.println(NumberOf1Between1AndN_Solution(n));
        }
    }
}