Costo mínimo para subir escaleras

    
Costo mínimo para subir escaleras (Java, Python, PHP, C++, Javascript).

Introducción
   
Min Cost Climbing Stairs es un problema de programación que se utiliza en las entrevistas de Google. En este problema, se nos da un arreglo de números que representan el costo de subir cada escalón de una escalera. El objetivo es encontrar el camino más barato para llegar a la cima de la escalera.

En este artículo, cubriremos los siguientes temas:

✅ Una explicación del problema
✅ Una solución eficiente
✅ Implementaciones en Java, Python, PHP, C++ y JavaScript



Problema

El ejercicio consiste en encontrar el costo mínimo de subir una escalera con n escalones, donde cada escalón tiene un costo asociado. Se puede subir uno o dos escalones a la vez, y el objetivo es llegar al último escalón con el menor costo posible.


En el ejemplo se puede apreciar que dada una escalera  con costos asociados, uno puede subir uno o dos escalones. 

Entre el primer y segundo escalón(1 y 100 respectivamentfe), el costo más bajo es el primero, de valor uno, entonces se sube un escalón. 
        
Pasos para realizar el algoritmo:
1.- Comprobar la cantidad de elementos de la escalera (del array cost), si es cero, significa que no hay escalones y el ejercicio retorna cero. Si solo hay un escalón, el ejercicio retorna el costo asociado a ese escalón.

2.- Guardar los costos asociados del primer y segundo escalón, e inicializar en 0 el total de la suma de los costos mínimos para subir la escalera.

3.- Calcular el costo mínimo, esto se hace a partir del tercer escalón hasta el último. Por cada escalón, se suma el costo asociado del escalón actual más el costo mínimo entre el primer y el segundo escalón anterior.

4.- Se actualiza el primer y segundo escalón para que contengan los costos mínimos de llegar al escalón actual. El primer escalón pasa a tener el valor del segundo, y el segundo escalón pasa a tener el valor del total de costos.

5.- Finalmente, se devuelve el total del costo mínimo de llegar al último escalón, que es el menor valor entre los costos mínimos de llegar al penúltimo y al último escalón.
            

Código en Java

public class Solution {
 
    public static int minCostClimbingStairs(int[] cost) {
        //paso#1
        int size = cost.length;
        if (size == 0) return 0;
        if (size == 1) return cost[0];
 
        //paso#2
        int primerEscalonPrevio = cost[0];
        int segundoEscalonPrevio = cost[1];
        int total = 0;
 
        //paso#3
        for (int i = 2; i < size; i++) {
            total = cost[i] + Math.min(primerEscalonPrevio, segundoEscalonPrevio);
 
            //paso#4
            primerEscalonPrevio = segundoEscalonPrevio;
            segundoEscalonPrevio = total;
        }
 
        //paso#5
        total = Math.min(primerEscalonPrevio, segundoEscalonPrevio);
 
        return total;
    }
}

Código en php

class Solution {
 
    /**
     * @param Integer[] $cost
     * @return Integer
     */
    function minCostClimbingStairs($cost) {
 
        //paso#1
        $size=count($cost);
        if($size==0) return 0;
        if($size==1) return $cost[0];
 
        //paso#2
        $primerEscalonPrevio=$cost[0];
        $segundoEscalonPrevio=$cost[1];
        $total=0;
 
        //paso#3
        for ($i = 2; $i < $size; $i++) {
            $total= $cost[$i]+ min($primerEscalonPrevio,$segundoEscalonPrevio);
 
            //paso#4
            $primerEscalonPrevio=$segundoEscalonPrevio;
            $segundoEscalonPrevio=$total;
        }
 
        //paso#5
        $total=min($primerEscalonPrevio,$segundoEscalonPrevio);
 
        return $total;
 
    }
}

Código en Python

class Solution:
    def minCostClimbingStairs(self, cost):
        # paso#1
        size = len(cost)
        if size == 0: return 0
        if size == 1: return cost[0]
 
        # paso#2
        primer_escalon_previo = cost[0]
        segundo_escalon_previo = cost[1]
        total = 0
 
        # paso#3
        for i in range(2, size):
            total = cost[i] + min(primer_escalon_previo, segundo_escalon_previo)
 
            # paso#4
            primer_escalon_previo = segundo_escalon_previo
            segundo_escalon_previo = total
 
        # paso#5
        total = min(primer_escalon_previo, segundo_escalon_previo)
 
        return total

Código en C++

class Solution {
public:
  int minCostClimbingStairs(std::vector<int>& cost) {
    // Paso #1
    int size = cost.size();
    if (size == 0) return 0;
    if (size == 1) return cost[0];
 
    // Paso #2
    int primerEscalonPrevio = cost[0];
    int segundoEscalonPrevio = cost[1];
    int total = 0;
 
    // Paso #3
    for (int i = 2; i < size; i++) {
      total = cost[i] + std::min(primerEscalonPrevio, segundoEscalonPrevio);
 
      // Paso #4
      primerEscalonPrevio = segundoEscalonPrevio;
      segundoEscalonPrevio = total;
    }
 
    // Paso #5
    total = std::min(primerEscalonPrevio, segundoEscalonPrevio);
 
    return total;
  }
};

Código en JavaScript

/**
    * @param {number[]} cost
    * @return {number}
    */
   var minCostClimbingStairs = function(cost) {
       // Paso #1
       const size = cost.length;
       if (size === 0) return 0;
       if (size === 1) return cost[0];
    
       // Paso #2
       let primerEscalonPrevio = cost[0];
       let segundoEscalonPrevio = cost[1];
       let total = 0;
    
       // Paso #3
       for (let i = 2; i < size; i++) {
         total = cost[i] + Math.min(primerEscalonPrevio, segundoEscalonPrevio);
         // Paso #4
         primerEscalonPrevio = segundoEscalonPrevio;
         segundoEscalonPrevio = total;
       }
    
       // Paso #5
       total = Math.min(primerEscalonPrevio, segundoEscalonPrevio);
    
       return total;
   };

        
    
Conclusión
En esta entrada de blog, hemos visto una solución a Min Cost Climbing Stairs en varios lenguajes de programación. La solución óptima se puede encontrar utilizando un enfoque simple y directo que no requiere programación dinámica.

Este problema es un buen ejemplo de cómo los problemas de optimización pueden resolverse de forma eficiente sin recurrir a técnicas complejas. También es un buen ejercicio para practicar la resolución de problemas de programación.