輸入N(1 <= N <= 10^9)Output
輸出包含1的個數(shù)Input示例
12Output示例
5轉：點擊打開鏈接一道基礎的數(shù)位dp，當作入門題也挺好套用網上大多的數(shù)位dp模板，這里dp[pos]表示在沒有上界的限制條件下，從pos位到最低位能組成的數(shù)一共有多少個1，簡單來說，其實就是0到((10^pos) -1)有多少個1。數(shù)位dp其實就是一位一位的向下遞歸下去，每次枚舉一位上的每一個數(shù)， 這樣就可以構成一棵樹，比如就21這個上界舉例，dfs構成的搜索數(shù)如下圖所示：dfs中的pos表示當前搜索到達第幾位，num表示經過搜索樹層層遞歸下來的路徑上有幾個節(jié)點數(shù)字是1，limit就是模板中的標明是否是上界的標志。關于記憶化搜索的部分，當沒有l(wèi)imit限制的時候，就可以返回當前的保存的值，這里返回的num * ten[pos + 1] + dp[pos]值得仔細思考，其中ten[pos]表示10^pos，前一部分num*ten[pos]表示的是路徑上的數(shù)字為1的節(jié)點在子樹中會出現(xiàn)10^pos次，舉例來說，假設現(xiàn)在已經枚舉到百位之前枚舉的數(shù)字是131，那么接下來的需要計算的所有數(shù)字都是131xx，(也就是從是13100~13199）100個數(shù)字，那么也就是說前面路徑131中的兩個1一共出現(xiàn)了100次，所以要乘起來；后一部分dp[pos]很好理解，就是計算在13100到13199之間的數(shù)131xx在xx部分會出現(xiàn)的1的數(shù)目；這樣這兩部分加起來就是這條路搜索的答案。代碼：
#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int maxn = 10;int dp[maxn], a[maxn], ten[maxn] = {1};void init(){    for(int i = 1; i < maxn; i++)        ten[i] = ten[i-1]*10;}int dfs(int pos, int num, int limit){    cnt++;    if(pos == -1) return num;    if(!limit && dp[pos] != -1) return num*ten[pos+1]+dp[pos];    int up = limit ? a[pos] : 9;    int tmp = 0;    for(int i = 0; i <= up; i++)        tmp += dfs(pos-1, num+(i==1), limit && a[pos] == i);    if(!limit) dp[pos] = tmp;    return tmp;}int solve(int x){    int pos = 0;    while(x)    {        a[pos++] = x%10;        x /= 10;    }    return dfs(pos-1, 0, 1);}int main(void){    int n;    init();    memset(dp, -1, sizeof(dp));    while(cin >> n)        PRintf("%d/n", solve(n));    return 0;}這道題的另一種數(shù)位dp的寫法感覺更好一些dp[pos][num]記錄的是當前長度前面有num個1的情況下1的總數(shù)
#include<iostream>#include<cstring>#include<cstdio>using namespace std;typedef long long ll;const int maxn = 20;ll dp[maxn][maxn], a[maxn];ll dfs(int pos, int num, int limit){    if(pos == -1) return num;    if(!limit && dp[pos][num] != -1) return dp[pos][num];    int up = limit ? a[pos] : 9;    ll tmp = 0;    for(int i = 0; i <= up; i++)        tmp += dfs(pos-1, num+(i==1), limit && i == a[pos]);    if(!limit) dp[pos][num] = tmp;    return tmp;}ll solve(ll x){    int pos = 0;    while(x)    {        a[pos++] = x%10;        x /= 10;    }    return dfs(pos-1, 0,  1);}int main(void){    ll n;    memset(dp, -1, sizeof(dp));    while(cin >> n)        printf("%lld/n", solve(n));    return 0;}