题目描述

leetcode902. 最大为 N 的数字组合

给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如，如果 digits = ['1','3','5']，我们可以写数字，如 '13', '551', 和 '1351315'。

返回 可以生成的小于或等于给定整数 n 的正整数的个数 。

 

示例 1：

输入：digits = ["1","3","5","7"], n = 100
输出：20
解释：
可写出的 20 个数字是：
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.

示例 2：

输入：digits = ["1","4","9"], n = 1000000000
输出：29523
解释：
我们可以写 3 个一位数字，9 个两位数字，27 个三位数字，
81 个四位数字，243 个五位数字，729 个六位数字，
2187 个七位数字，6561 个八位数字和 19683 个九位数字。
总共，可以使用D中的数字写出 29523 个整数。

示例 3:

输入：digits = ["7"], n = 8
输出：1

 

提示：

  • 1 <= digits.length <= 9
  • digits[i].length == 1
  • digits[i] 是从 '1' 到 '9' 的数
  • digits 中的所有值都 不同 
  • digits 按 非递减顺序 排列
  • 1 <= n <= 109

题解——直观解释：数位DP/记忆化搜索，C++ 0ms

思路

我们通过几个简单的子问题来解决这道题。

  • 去掉<=n的条件，只是求位数为k的满足条件的数，怎样求解？显然，由于大小不限而且digits中没有0，每一位都有digits.size()种选择，那么，总共就有digits.size()^k个数(排列组合/乘法原理)。
  • 加入<=n的限制，变为求位数与n相同的<=n的数，如果第一位已经确定
    • 假如第一位严格小于n的第一位，那么，后面的几位又不受限制了，这样，相当于求位数为k-1的由digits组成的数。根据上面的结论，就应当是digits.size()^(k-1)。
    • 假如第一位严格大于n的第一位，那么，无论后面怎么排列，都不能产生<n的数了，答案就是0。
    • 假如第一位==n的第一位，那么，要求从第二位开始的数<=n从第二位开始的数。这就产生了递归。

根据上面的推断，有这样的思路：设n的位数为cnt，位数为1~cnt-1的数的个数可以直接求出，也就是digits.size()^k，由于后面要经常用到，我们将它记忆下来，作为一个memo数组。那么，我们只需要求位数为cnt的<=n的由digits组成的数了。根据上面的推断，我们编写递归函数dfs，对于每一位，遍历digits，如果小于limit[k]，直接加上memo[k]，如果等于limit[k]，搜索下一位，如果大于，就是0。
具体细节(位数的对应关系)可以看一下这张图，这是在digits=[1,4,7],n=12345时生成的limit和memo数组。
image.png
为了方便写，我传入的是第k位数(从1开始)，并找到limit和memo中对应的位置比较即可，这里不多讲了。

记忆化搜索写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<int> nums,memo,limit;
    int cnt=0;//cnt为位数
    int dfs(int k)//搜索第k位数
    {
        if(k==cnt+1)//超出，应该返回1
            return 1;
        int res=0;
        for(int n:nums)
            if(n<limit[cnt-k])//如果小于对应位，直接加上memo
                res+=memo[cnt-k];
            else if(n==limit[cnt-k])//如果等于，搜索下一位
                res+=dfs(k+1);
        return res;
    }
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        for(auto &s:digits)//将digits转化为数
            nums.push_back(stoi(s));
        for(int res=1;n;++cnt,res*=digits.size())
        {
            memo.push_back(res);//digits.size()^k
            limit.push_back(n%10);//位数拆分
            n/=10;
        }
        return accumulate(memo.begin()+1,memo.end(),0)+dfs(1);//位数小的答案和位数相同的答案相加返回
    }
};

动态规划写法

将自前往后搜索改为自后往前记录，可以将记忆化搜索改成动态规划，这两者时空复杂度相同，代码也高度相似，就不多说了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        vector<int> limit,nums,memo;
        int cnt=0,res=1;
        for(int res=1;n;++cnt,res*=digits.size())
        {
            limit.push_back(n%10);
            memo.push_back(res);
            n/=10;
        }
        for(auto &s:digits)
            nums.push_back(stoi(s));
        vector<int> dp(cnt);//将dp数组初始化为n的位数
        for(int i=0;i<cnt;++i)
        {
            for(int num:nums)
                if(num<limit[i])
                    dp[i]+=memo[i];
                else if(num==limit[i])
                    dp[i]+=i?dp[i-1]:1;
        }
        return accumulate(memo.begin()+1,memo.end(),0)+dp.back();
    }
};