[디지털 DP] [357. Count Numbers with Unique Digits]

제목 링크:https://leetcode.com/problems/count-numbers-with-unique-digits/#/description
class Solution {
public:
    int bit[15]={0};    //       ,999999...
    int dp[15]={0};     //          
    int a[10]={0};      //            
    int countNumbersWithUniqueDigits(int n) {
        if(n>=10) return 8877691;
        return solve(n);
    }
    //  bit     ,n=2,99
    int solve(int n){
        int pos=0;
        while(n){
            bit[++pos]=9;
            n--;
        }
        return dfs(pos,true,true);
    }
    //      
    int dfs(int len,bool isMax,bool isFirst){
        if(len==0) return 1;
        // if(!isMax&&dp[len]>=0) return dp[len];
        int cnt=0;
        int maxNum=9;
        for(int i=0;i<=maxNum;i++){
            if(a[i]) continue;
            a[i]=1;
            if(isFirst&&i==0) a[i]=0;
            cnt+=dfs(len-1,i==maxNum,isFirst&&i==0);
            a[i]=0;
        }
        if(!isMax) dp[len]=cnt;
        return cnt;
    }
};

좋은 웹페이지 즐겨찾기