1 class Solution {
 2 public:
 3     int dp[30][30];
 4     int digit[30];
 5 
 6     int dfs(int l, int cnt, bool flag) {
 7         if(l == 0) return cnt;
 8         if(!flag && ~dp[l][cnt]) return dp[l][cnt];
 9         int pos = flag ? digit[l] : 9;
10         int ret = 0;
11         for(int i = 0; i <= pos; i++) {
12             ret += dfs(l-1, cnt+(i==1), flag&&(pos==i));
13         }
14         if(!flag) dp[l][cnt] = ret;
15         return ret;
16     }
17 
18     int countDigitOne(int n) {
19         memset(dp, -1, sizeof(dp));
20         int pos = 0;
21         while(n) {
22             digit[++pos] = n % 10;
23             n /= 10;
24         }
25         return dfs(pos, 0, true);
26     }
27 };