Movimientos mínimos para igualar M y N mediante la suma repetida de divisores excepto 1 | Set-2 (Programación Dinámica)

Dados dos números enteros N y M , la tarea es calcular el número mínimo de movimientos para cambiar N a M , donde En un movimiento se permite sumar cualquier divisor del valor actual de N a N mismo excepto 1. Imprimir “-1 ” si no es posible.

Ejemplo : 

Entrada: N = 4, M = 24
Salida: 5
Explicación: El valor dado de N se puede convertir en M siguiendo los siguientes pasos: (4)+2 -> (6)+2 -> (8)+4 -> (12)+6 -> (18)+6 -> 24. Por lo tanto, el número de movimientos es 5, que es el mínimo posible.

Entrada : N = 4, M = 576
Salida : 14

Enfoque BFS: el problema dado ya se ha discutido en el Conjunto 1 de este artículo que usa el recorrido primero en anchura para resolver el problema dado. 

Enfoque : este artículo se centró en un enfoque diferente basado en la programación dinámica . A continuación se detallan los pasos a seguir:

• Cree una array 1-D dp[] , donde dp[i] almacena la cantidad mínima de operaciones para llegar a i desde N . Inicialmente, dp[N+1… M] = {INT_MAX} y dp[N] = 0 .
• Iterar a través del rango [N, M] usando una variable i y para cada i , iterar a través de todos los factores del número dado i . Para un factor X , la relación DP se puede definir de la siguiente manera:

dp[i + X] = min( dp[i], dp[i + X])

• El valor almacenado en dp[M] es la respuesta requerida.

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

// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum count of
// operations to convert N to M
int minOperationCnt(int N, int M)
{
 
    // Stores the DP state of the array
    int dp[M + 1];
 
    // Initialize each index with INT_MAX
    for (int i = N + 1; i <= M; i++) {
        dp[i] = INT_MAX;
    }
 
    // Initial condition
    dp[N] = 0;
 
    // Loop to iterate over range [N, M]
    for (int i = N; i <= M; i++) {
 
        // Check if this position
// can be reached or not
        if (dp[i] == INT_MAX) {
            continue;
        }
 
        // Loop to iterate through all divisors
        // of the current value i
        for (int j = 2; j * j <= i; j++) {
 
            // If j is a divisor of i
            if (i % j == 0) {
                if (i + j <= M) {
 
                    // Update the value of dp[i + j]
                    dp[i + j] = min(dp[i + j], dp[i] + 1);
                }
 
                // Check for value i / j;
                if (i + i / j <= M) {
 
                    // Update the value of dp[i + i/j]
                    dp[i + i / j]
                        = min(dp[i + i / j], dp[i] + 1);
                }
            }
        }
    }
 
    // Return Answer
    return (dp[M] == INT_MAX) ? -1 : dp[M];
}
 
// Driver Code
int main()
{
    int N = 4;
    int M = 576;
 
    cout << minOperationCnt(N, M);
 
    return 0;
}

// Java implementation for the above approach
class GFG {
 
    // Function to find the minimum count of
    // operations to convert N to M
    public static int minOperationCnt(int N, int M) {
 
        // Stores the DP state of the array
        int[] dp = new int[M + 1];
 
        // Initialize each index with INT_MAX
        for (int i = N + 1; i <= M; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
 
        // Initial condition
        dp[N] = 0;
 
        // Loop to iterate over range [N, M]
        for (int i = N; i <= M; i++) {
 
            // Check if this position
            // can be reached or not
            if (dp[i] == Integer.MAX_VALUE) {
                continue;
            }
 
            // Loop to iterate through all divisors
            // of the current value i
            for (int j = 2; j * j <= i; j++) {
 
                // If j is a divisor of i
                if (i % j == 0) {
                    if (i + j <= M) {
 
                        // Update the value of dp[i + j]
                        dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
                    }
 
                    // Check for value i / j;
                    if (i + i / j <= M) {
 
                        // Update the value of dp[i + i/j]
                        dp[i + i / j] = Math.min(dp[i + i / j], dp[i] + 1);
                    }
                }
            }
        }
 
        // Return Answer
        return (dp[M] == Integer.MAX_VALUE) ? -1 : dp[M];
    }
 
    // Driver Code
    public static void main(String args[]) {
        int N = 4;
        int M = 576;
 
        System.out.println(minOperationCnt(N, M));
    }
}
 
// This code is contributed by saurabh_jaiswal.

# python implementation for the above approach
import math
 
INT_MAX = 2147483647
 
# Function to find the minimum count of
# operations to convert N to M
def minOperationCnt(N, M):
 
     # Stores the DP state of the array
    dp = [0 for _ in range(M + 1)]
 
    # Initialize each index with INT_MAX
    for i in range(N+1, M+1):
        dp[i] = INT_MAX
 
        # Initial condition
    dp[N] = 0
 
    # Loop to iterate over range [N, M]
    for i in range(N, M+1):
 
                # Check if this position
        # can be reached or not
        if (dp[i] == INT_MAX):
            continue
 
            # Loop to iterate through all divisors
            # of the current value i
        for j in range(2, int(math.sqrt(i))+1):
 
                        # If j is a divisor of i
            if (i % j == 0):
                if (i + j <= M):
 
                     # Update the value of dp[i + j]
                    dp[i + j] = min(dp[i + j], dp[i] + 1)
 
                    # Check for value i / j;
                if (i + i // j <= M):
 
                     # Update the value of dp[i + i/j]
                    dp[i + i // j] = min(dp[i + i // j], dp[i] + 1)
 
        # Return Answer
    if dp[M] == INT_MAX:
        return -1
    else:
        return dp[M]
 
# Driver Code
if __name__ == "__main__":
 
    N = 4
    M = 576
 
    print(minOperationCnt(N, M))
 
    # This code is contributed by rakeshsahni

// C# implementation for the above approach
using System;
class GFG
{
 
  // Function to find the minimum count of
  // operations to convert N to M
  public static int minOperationCnt(int N, int M)
  {
 
    // Stores the DP state of the array
    int[] dp = new int[M + 1];
 
    // Initialize each index with INT_MAX
    for (int i = N + 1; i <= M; i++)
    {
      dp[i] = int.MaxValue;
    }
 
    // Initial condition
    dp[N] = 0;
 
    // Loop to iterate over range [N, M]
    for (int i = N; i <= M; i++)
    {
 
      // Check if this position
      // can be reached or not
      if (dp[i] == int.MaxValue)
      {
        continue;
      }
 
      // Loop to iterate through all divisors
      // of the current value i
      for (int j = 2; j * j <= i; j++)
      {
 
        // If j is a divisor of i
        if (i % j == 0)
        {
          if (i + j <= M)
          {
 
            // Update the value of dp[i + j]
            dp[i + j] = Math.Min(dp[i + j], dp[i] + 1);
          }
 
          // Check for value i / j;
          if (i + i / j <= M)
          {
 
            // Update the value of dp[i + i/j]
            dp[i + i / j] = Math.Min(dp[i + i / j], dp[i] + 1);
          }
        }
      }
    }
 
    // Return Answer
    return (dp[M] == int.MaxValue) ? -1 : dp[M];
  }
 
  // Driver Code
  public static void Main()
  {
    int N = 4;
    int M = 576;
 
    Console.Write(minOperationCnt(N, M));
  }
}
 
// This code is contributed by saurabh_jaiswal.

<script>
 
       // JavaScript Program to implement
       // the above approach
 
       // Function to find the minimum count of
       // operations to convert N to M
       function minOperationCnt(N, M) {
 
           // Stores the DP state of the array
           let dp = new Array(M + 1)
 
           // Initialize each index with INT_MAX
           for (let i = N + 1; i <= M; i++) {
               dp[i] = Number.MAX_VALUE;
           }
 
           // Initial condition
           dp[N] = 0;
 
           // Loop to iterate over range [N, M]
           for (let i = N; i <= M; i++) {
 
               // Check if this position
               // can be reached or not
               if (dp[i] == Number.MAX_VALUE) {
                   continue;
               }
 
               // Loop to iterate through all divisors
               // of the current value i
               for (let j = 2; j * j <= i; j++) {
 
                   // If j is a divisor of i
                   if (i % j == 0) {
                       if (i + j <= M) {
 
                           // Update the value of dp[i + j]
                           dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
                       }
 
                       // Check for value i / j;
                       if (i + i / j <= M) {
 
                           // Update the value of dp[i + i/j]
                           dp[i + i / j]
                               = Math.min(dp[i + i / j], dp[i] + 1);
                       }
                   }
               }
           }
 
           // Return Answer
           return (dp[M] == Number.MAX_VALUE) ? -1 : dp[M];
       }
 
       // Driver Code
       let N = 4;
       let M = 576;
 
       document.write(minOperationCnt(N, M));
 
   // This code is contributed by Potta Lokesh
   </script>

14

Complejidad de tiempo: O((M – N)*√(M – N))
Espacio auxiliar: O(M)