题解

记忆化dfs

C++ 代码

#include <iostream>
#include <cstring> 

using namespace std;

const int N = 20;

int dp[N][N], n;
int a[N];

int dfs(int pos, int state, bool limit)
{
    if (pos == -1) return state;

    if (!limit && dp[pos][state] != -1) return dp[pos][state];

    int tmp = 0;
    int up = limit ? a[pos] : 9;
    for (int i = 0; i <= up; i ++ )
    {
        if (i == 1) tmp += dfs(pos - 1, state + 1, limit && i == a[pos]);
        else tmp += dfs(pos - 1, state, limit && i == a[pos]);
    }

    if (!limit) dp[pos][state] = tmp;

    return tmp;
}

int solve(int x)
{
    int pos = 0;
    while (x != 0)
    {
        a[pos ++ ] = x % 10;
        x /= 10;
    }
    dfs(pos - 1, 0, true);
}

int main()
{
    cin >> n;
    memset(dp, -1, sizeof dp);
    cout << solve(n) << endl;

    return 0;
}