LeetCode 357. 计算各个位数不同的数字个数

我就是我 2023-07-03 07:22 22阅读 0赞

### 解题思路 ###

非常经典的数位dp。麻烦的地方在于要处理前导0.例如010这样的数据如果不处理前导0的话，会认为有两个0.  
数位dp的思路这里不再阐述。  
dp\[pos\]\[sta\]表示前pos位，状态为sta满足题意的数的个数。  
注意使用位运算来查看有没有重复的数。

### 代码 ###

class Solution { 
    public:
        long long dp[30][1<<11];
        int bit[30];
        bool check(int sta,int i)
        { 
            return sta&(1<<(i));
        }
        long long dfs(int pos,int sta,bool limit,bool zero)
        { 
            if(pos==-1) return 1;
            if(limit==0&&zero==0&&dp[pos][sta]!=-1) return dp[pos][sta];
            int up=limit?bit[pos]:9;
            long long ans=0;
            for(int i=0;i<=up;i++)
            { 
                if(zero&&i==0)
                { 
                    ans+=dfs(pos-1,sta,limit&&i==up,zero&&i==0);
                }
                else
                { 
                    if(check(sta,i))
                    { 
                        continue;
                        //cout<<sta<<" "<<i<<endl;
                        //ans+=dfs(pos-1,sta|(1<<i),sta&&0,limit&&i==up,zero&&i==0);
                    }
                    else
                    { 
                        ans+=dfs(pos-1,sta|(1<<(i)),limit&&i==up,zero&&i==0);
                    }
                }
            }
            if(limit==0&&zero==0) dp[pos][sta]=ans;
            return ans;
        }
        long long solve(long long x)
        { 
            int k=0;
            while(x)
            { 
                bit[k++]=x%10;
                x/=10;
            }
            return dfs(k-1,0,1,1);
        }
        int countNumbersWithUniqueDigits(int n) { 
            long long x=1;
            memset(dp,-1,sizeof(dp));
            while(n)
            { 
                x*=10;
                n--;
            }
            return solve(x-1);
        }
    };