leetcode--357--计算各个位数不同的数字个数

题目：
给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。

示例:

输入: 2
输出: 91
解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。

链接：https://leetcode-cn.com/problems/count-numbers-with-unique-digits

思路：
1、本题是一套排列组合的题目，可以通过找规律来找到动态规划函数

f(0)=1 
f(1)=10
f(2)=9*9+f(1)
f(3)=9*9*8+f(2)
f(4)=9*9*8*7+f(3)

Python代码：

class Solution(object):
    def countNumbersWithUniqueDigits(self, n):
        """
        :type n: int
        :rtype: int
        """
        # f(0)=1 
        # f(1)=10
        # f(2)=9*9+f(1)
        # f(3)=9*9*8+f(2)
        # f(4)=9*9*8*7+f(3)

        dp = [1, 10]
        if n<2:
            return dp[n]

        for i in range(2, n+1):
            j = i-1
            item = 9
            while j>0:
                item *= (10-j)
                j -= 1
            dp.append(item + dp[i-1])
        return dp[n]

C++代码：

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        // f(0)=1 
        // f(1)=10
        // f(2)=9*9+f(1)
        // f(3)=9*9*8+f(2)
        // f(4)=9*9*8*7+f(3)

        vector<int> dp{1, 10};
        if (n<2) return dp[n];

        for (int i=2; i<=n; i++){
            int j = i-1;
            int item=9;
            while (j>0){
                item *= (10-j);
                j -= 1;
            }
            item += dp[i-1];
            dp.push_back(item);
        }
        return dp[n];
        
    }
};