1 int dp[11][11];
 2 int a[11];
 3 
 4 class Solution {
 5 public:
 6     long long dfs(int eq,int dep,int sum)
 7     {
 8         if(!dep)return sum;
 9         if(~dp[dep][sum]&&!eq)return dp[dep][sum];
10         int mx=eq==1?a[dep]:9;
11         long long ret=0;
12         for(int i=0;i<=mx;i++)
13         {
14             ret+=dfs((i==mx)&&eq,dep-1,(sum+((i==1)?1:0)));
15         }
16         if(!eq)dp[dep][sum]=ret;
17         return ret;
18     }
19     long long work(int n)
20     {
21         int tot=0;
22         memset(dp,-1,sizeof(dp));
23         for(;n;n/=10)a[++tot]=n%10;
24         return dfs(1,tot,0);
25     }
26     int countDigitOne(int n) {
27         return work(n);
28     }
29 };