LeetCode(902) -- Numbers At Most N Given Digit Set

Problem

Given an array of digits, you can write numbers using each digits[i] as many times as we want. For example, if digits = [‘1’,’3’,’5’], we may write numbers such as ‘13’, ‘551’, and ‘1351315’.

Return the number of positive integers that can be generated that are less than or equal to a given integer n.

Example 1:

Input: digits = ["1","3","5","7"], n = 100
Output: 20
Explanation: 
The 20 numbers that can be written are:
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.

My Solution

答案的dp方法实在是写得莫名其妙，大概的意思其实就是递归，但我不明白为什么管这种方法也叫dp。那如果这叫dp，那所有的递归都可以叫dp了。

class Solution {
    public int atMostNGivenDigitSet(String[] digits, int n) {
        String str = String.valueOf(n);
        int count = 0;
        // 首先加上组成的数字长度小于n的长度的所有可能。长度小于n的长度，那它一定小于n。从digits中，任选n-1个数字，任选n-2个数字……任选1个数字
        for (int i = 1; i < str.length(); i++) {
            count += Math.pow(digits.length, i);
        }
        //下面考虑长度等于n的长度的情况。
        //第一位，我们要挑一个小于等于n的第一位的数字；第二位，要挑一个小于等于n的第二位的数字……
        // 挑小于，还是等于呢？这两种情况是不一样的。如果挑小于，那后面的就能随便挑了，因为如果这一位小于的话，后面无论怎么挑都是小于的。而如果挑了等于，那么就要看后面有多少种挑法，也就是当前挑选这个数字有多少种挑法。
        
        return count + helper(digits, str, 0);
    }
    
    public int helper(String[] digits, String str, int index) {
        int ans = 0;
        int d = str.charAt(index) - '0';
        if (index == str.length() - 1) {
            for (int i = 0; i < digits.length; i++) {
                if (Integer.valueOf(digits[i]) <= d) {
                    ans++;
                }
            }
            return ans;
        }
        for (int i = 0; i < digits.length; i++) {
            if (Integer.valueOf(digits[i]) < d) {
                ans += Math.pow(digits.length, str.length() - index - 1);
            } else if (Integer.valueOf(digits[i]) == d) {
                ans += helper(digits, str, index + 1);
            }
        }
        return ans;
    }
}

我写了一个递归的方法，当探讨n的最后一位时，digits中有多少数字小于等于它，就有多少选选择方法。其他的数字要根据后面的结果确定。

The Best Solution