Removing Digits

You are given an integer n. On each step, you may subtract from it any one-digit number that appears in it.

How many steps are required to make the number equal to 0?

Example:

Input:  n = 27
Output: 5

Approach

C++

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int removingDigits(int n)
{

    vector<int> dp(n + 1, INF);
    dp[n] = 0;
    for (int i = n; i >= 1; i--)
    {
        int temp = i;
        while (temp > 0)
        {
            int d = temp % 10;
            temp /= 10;
            dp[i - d] = min(dp[i - d], dp[i] + 1);
        }
    }
    return dp[0];
}

int main()
{
    int n = 27;

    cout << removingDigits(n) << "\n";

    return 0;
}