【題解】CSES 1637 Removing Digits

【題目敘述】https://cses.fi/problemset/task/1637/
【解題想法】DP

#include <iostream>
#include <cstring>
using namespace std;
 
int n, dp[1000005];
 
int main() {
    cin >> n;
    memset(dp, 0x3F, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i <= n; i++){
        int tmp = i;
        while (tmp){
            dp[i] = min(dp[i], dp[i-(tmp%10)]+1);
            tmp /= 10;
        }
    }
    cout << dp[n] << "\n";
}
分享本文 Share with friends