[LeetCode]Dp357 计算各位不同的数的个数

传送门：https://leetcode-cn.com/problems/count-numbers-with-unique-digits/

题目

给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 。

示例:

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

解题思路：动态规划

设 的表示为： 区间内，各位数字不同的个数 。

举例： i=2 ,那么dp[2] 代表的意思就是 [10,100) 区间内各位数字不同的个数 。

求解 Dp[i+1] 时，其中 dp[i]是已知的 。
对前 i 个数不重复的一种情形分析可以知道：
前面 i 个数是不重复的，我们只要将最后一位在剩下的 10-i 里取一个就不会重复。并且会产生 10-i种结果 。由于前 **i** 个不重复的数字共有 **dp[i]**个序列，所以在**dp[i+1]**中会产生**dp[i]*(10-i)** 种序列情况 。

状态转移方程：

边界情况：

当 n=0 时，dp[0]=1 // 0
当 n=1 时，dp[1]=10 适用于状态转移方程 // 0 1 2 3 4 5 6 7 8 9
当 n=2 时，dp[2]=81 。 不适用于状态转移方程，需要特殊处理减去 9 个 原因就是 0 不能做十位

复杂度分析

时间复杂度：
因为要计算 n 次才能计算到 dp[n]。

空间复杂度：
需要开辟长度为 n 的数组。

代码

我的代码

class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if(n==0)return 1;
        if(n==1)return 10;
        int[]dp=new int[n+3];
        dp[0]=1;
        dp[1]=10;
        dp[2]=81;//为了简便直接在此给出具体值,省去内部判断
        int res=dp[1]+dp[2];
        for(int i=3;i<n+1;i++){
            dp[i]=dp[i-1]*(10-(i-1));
            res+=dp[i];
        }
        return res;
    }
}