題目描述
給定一個整數(shù) n舶得，計算所有小于等于 n 的非負整數(shù)中數(shù)字 1 出現(xiàn)的個數(shù)伸但。
示例1
輸入：
13
輸出：
6
解釋：
數(shù)字 1 出現(xiàn)在以下數(shù)字中: 1, 10, 11, 12, 13 。
題解
這題是我搜數(shù)位 dp 題目搜出來的元旬，于是我直接用數(shù)位 dp 方法把它過了赃绊，后來發(fā)現(xiàn)其實沒必要這么麻煩既峡，簡單的計算就能算出來了，這里兩個方法我都講一下碧查。
數(shù)學方法
我們不妨用 n = 12345 來舉個例子运敢。要求小于等于 n 的數(shù)字里有多少個 1 ，我們不妨轉(zhuǎn)換個角度忠售，看某一位數(shù)字是 1 的話传惠，有多少數(shù)字小于 n 。
例如從右向左數(shù)第 i = 2 位（數(shù)字 3 ）稻扬，如果這一位取 1 卦方，那么左邊 2 位如果取 0~11 ，那么右邊 2 位就沒有任何限制泰佳，從 0 取到 99 都行盼砍。如果左邊 2 位如果取 12 尘吗，那么就得考慮 n 中第 i 位是幾了，如果大于 1 浇坐，那么右邊 2 位還是沒有限制摇予；如果等于 1 ，那么右邊 2 位只能取 0~45 吗跋；如果等于 0 ，那就沒得取了宁昭。
下面這張圖是我打的草稿跌宛，看的更清楚一點：
一般化描述就是，考慮從右往左數(shù)第 i 位是 1 的數(shù)字數(shù)量积仗。那么 n 中第 i 位左邊部分的數(shù)字是 疆拘，而右邊可以取的數(shù)量是
，相乘就是總的數(shù)量
寂曹。如果左邊直接取最大值哎迄，那么就要考慮第 i 位數(shù)字是幾了，計算可以得到第 i 位數(shù)字為
隆圆，記為 x 漱挚。如果
，那么右邊無限制渺氧，有
種取法旨涝；如果
，那么右邊有
種取法侣背；如果
白华，那么右邊無法取，因為第 i 位都沒法取 1 贩耐。
綜上弧腥，令 ，那么答案就是：
數(shù)位dp
數(shù)位 dp 就麻煩許多了潮太，不想看的可以直接跳過了管搪。
首先我們從最高位開始往右遞歸計算，用 pos, count, limit 來表示計算到第 pos 位（從左往右消别，和數(shù)學方法不一樣）時抛蚤，已經(jīng)出現(xiàn)了 count 個 1 ，并且之后的數(shù)字有無限制（也就是能否取遍 0~9 ）寻狂，這種狀態(tài)之下方法數(shù)是多少岁经。
那么第 pos 位我們可以取的數(shù)字有哪些呢？如果 limit = 1 也就是有限制蛇券，那么只能取 0~n中第pos位缀壤，如果沒有限制那就取 0~9 樊拓。
假設(shè)第 pos 位取 1 ，那么 pos 就轉(zhuǎn)移到了 pos+1 塘慕，count 轉(zhuǎn)移到了 count+1 筋夏，limit 呢？只有當原來有限制图呢，并且第 pos 位正好取了最大值也就是 n 中第 pos 位數(shù)字時条篷，limit 還是 1 ，否則的話限制取消蛤织，后面的數(shù)字隨便取赴叹。如果第 pos 位不取 1 ，那么除了 count 不變以外指蚜，其他兩個狀態(tài)還是跟上面一樣轉(zhuǎn)移乞巧。
終止狀態(tài)的話，如果遍歷到了最后一位結(jié)束摊鸡，就返回 count 數(shù)量就行了绽媒，表示當前數(shù)字中有 count 個 1 。
這樣的話會有很多重復(fù)計算的狀態(tài)免猾，所以需要用到記憶化搜索是辕，用 dp[pos][count] 來保存 pos, count, limit=0 狀態(tài)下的答案。為什么只保存 limit=0 的答案呢掸刊？因為只有無限制的情況下免糕，后面的數(shù)字才能隨便取，跟 n 是多少沒有關(guān)系忧侧。否則的話 n 變了后面的值就會受限于 n 石窑，那么就不是一個定值了，沒法保存蚓炬。
那么 limit=1 不保存的話會不會超時呢松逊？不會的，因為每一位只有一種取法會使得后面的數(shù)字繼續(xù)有限制肯夏，所以整體上來看经宏，有限制的狀態(tài)個數(shù)是個常數(shù)，并不需要擔心超時驯击。
代碼
數(shù)學方法（c++）
class Solution {
public:
int countDigitOne(int n) {
int res = 0;
for (long i = 1; i <= n; i *= 10) {
res += n / (i * 10) * i;
int x = (n / i) % 10;
res += x > 1 ? i : (n % i + 1) * x;
}
return res;
}
};
數(shù)位dp（c++）
class Solution {
public:
int a[14];
int dp[14][14];
int dfs(int pos, int count, int limit) {
if (!pos) return count;
if (!limit && dp[pos][count] != -1) return dp[pos][count];
int res = 0, ub = limit ? a[pos] : 9;
for (int i = 0; i <= ub; ++i) {
res += dfs(pos-1, count+(i==1), limit&&i==a[pos]);
}
return limit ? res : dp[pos][count]=res;
}
int countDigitOne(int n) {
memset(dp, -1, sizeof dp);
int len = 0;
while (n) {
a[++len] = n % 10;
n /= 10;
}
return dfs(len, 0, 1);
}
};
數(shù)學方法（python）
class Solution:
def countDigitOne(self, n: int) -> int:
res, i = 0, 1
while i <= n:
res += n // (i * 10) * i
x = (n // i) % 10
res += i if x > 1 else (n % i + 1) * x
i *= 10
return res
