Número mínimo de operaciones para reducir N a 0 restando cualquier dígito de N

Dado un número N , la tarea es encontrar el número mínimo de operaciones requeridas para reducir el número N a cero restando el número dado por cualquier dígito presente en él.

Ejemplos: 

Entrada: N = 4 
Salida: 1 
Explicación: 
Aquí 4 es el único dígito presente, por lo tanto, 4 – 4 = 0 y solo se requiere una operación.

Entrada: N = 17 
Salida: 3 
Explicación: 
El número entero dado es 17 y los pasos de reducción son: 
17 -> 17 – 7 = 10 
10 -> 10 – 1 = 9 
9 -> 9 – 9 = 0. 
Por lo tanto, 3 operaciones son requeridos. 

Enfoque: Este problema se puede resolver usando Programación Dinámica . 
Para cualquier número dado N , recorra cada dígito en N y verifique recursivamente restando cada dígito uno por uno hasta que N se reduzca a 0 . Pero realizar la recursividad hará que la complejidad temporal del enfoque sea exponencial.
Por lo tanto, la idea es usar una array (por ejemplo , dp[] ) de tamaño (N + 1) tal que dp[i] almacene el número mínimo de operaciones necesarias para reducir i a 0 . 

Para cada dígito x en el número N , la relación de recurrencia utilizada viene dada por:  

dp[i] = min(dp[i], dp[ix] + 1), 
donde dp[i] almacenará el número mínimo de operaciones necesarias para reducir i a 0 . 
 

Usaremos el enfoque ascendente para llenar la array dp[] de 0 a N y luego dp[N] dará el número mínimo de operaciones para N.

A continuación se muestra la implementación del enfoque anterior:  

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to reduce an integer N
// to Zero in minimum operations by
// removing digits from N
int reduceZero(int N)
{
    // Initialise dp[] to steps
    vector<int> dp(N + 1, 1e9);
 
    dp[0] = 0;
 
    // Iterate for all elements
    for (int i = 0; i <= N; i++) {
 
        // For each digit in number i
        for (char c : to_string(i)) {
 
            // Either select the number
            // or do not select it
            dp[i] = min(dp[i],
                        dp[i - (c - '0')]
                            + 1);
        }
    }
 
    // dp[N] will give minimum
    // step for N
    return dp[N];
}
 
// Driver Code
int main()
{
    // Given Number
    int N = 25;
 
    // Function Call
    cout << reduceZero(N);
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG{
 
// Function to reduce an integer N
// to Zero in minimum operations by
// removing digits from N
static int reduceZero(int N)
{
    // Initialise dp[] to steps
    int []dp = new int[N + 1];
    for (int i = 0; i <= N; i++)
        dp[i] = (int) 1e9;
    dp[0] = 0;
 
    // Iterate for all elements
    for (int i = 0; i <= N; i++)
    {
 
        // For each digit in number i
        for (char c : String.valueOf(i).toCharArray())
        {
 
            // Either select the number
            // or do not select it
            dp[i] = Math.min(dp[i],
                             dp[i - (c - '0')] + 1);
        }
    }
 
    // dp[N] will give minimum
    // step for N
    return dp[N];
}
 
// Driver Code
public static void main(String[] args)
{
    // Given Number
    int N = 25;
 
    // Function Call
    System.out.print(reduceZero(N));
}
}
 
// This code is contributed by amal kumar choubey

# Python3 program for the above approach
 
# Function to reduce an integer N
# to Zero in minimum operations by
# removing digits from N
def reduceZero(N):
     
    # Initialise dp[] to steps
    dp = [1e9 for i in range(N + 1)]
 
    dp[0] = 0
 
    # Iterate for all elements
    for i in range(N + 1):
         
        # For each digit in number i
        for c in str(i):
             
            # Either select the number
            # or do not select it
            dp[i] = min(dp[i],
                        dp[i - (ord(c) - 48)] + 1)
 
    # dp[N] will give minimum
    # step for N
    return dp[N]
 
# Driver Code
N = 25
 
# Function Call
print(reduceZero(N))
 
# This code is contributed by Sanjit_Prasad

// C# program for the above approach
using System;
class GFG{
 
// Function to reduce an integer N
// to Zero in minimum operations by
// removing digits from N
static int reduceZero(int N)
{
    // Initialise []dp to steps
    int []dp = new int[N + 1];
    for (int i = 0; i <= N; i++)
        dp[i] = (int) 1e9;
    dp[0] = 0;
 
    // Iterate for all elements
    for (int i = 0; i <= N; i++)
    {
 
        // For each digit in number i
        foreach (char c in String.Join("", i).ToCharArray())
        {
 
            // Either select the number
            // or do not select it
            dp[i] = Math.Min(dp[i],
                             dp[i - (c - '0')] + 1);
        }
    }
 
    // dp[N] will give minimum
    // step for N
    return dp[N];
}
 
// Driver Code
public static void Main(String[] args)
{
    // Given Number
    int N = 25;
 
    // Function Call
    Console.Write(reduceZero(N));
}
}
 
// This code is contributed by amal kumar choubey

<script>
 
// Javascript program for the above approach
 
// Function to reduce an integer N
// to Zero in minimum operations by
// removing digits from N
function reduceZero(N)
{
    // Initialise dp[] to steps
    var dp = Array(N + 1).fill(1000000000);
 
    dp[0] = 0;
 
    // Iterate for all elements
    for (var i = 0; i <= N; i++) {
 
        // For each digit in number i
        for (var j =0; j< i.toString().length; j++)
        {
            // Either select the number
            // or do not select it
            dp[i] = Math.min(dp[i],
                        dp[i - (i.toString()[j] - '0')]
                            + 1);
        }
    }
 
    // dp[N] will give minimum
    // step for N
    return dp[N];
}
 
// Driver Code
 
// Given Number
var N = 25;
 
// Function Call
document.write( reduceZero(N));
 
</script>

5

Complejidad temporal: O(N)  
Espacio auxiliar: O(N)