Costo mínimo para llegar a la parte superior del piso subiendo escaleras

Dados N enteros no negativos, lo que significa el costo del movimiento de cada escalera. Pagando el costo en el paso i-ésimo, puede subir uno o dos pasos. Dado que uno puede comenzar desde el 0-el escalón o desde el 1-el escalón, la tarea es encontrar el costo mínimo para llegar a la parte superior del piso (N+1) subiendo N escaleras. 

Ejemplos: 

Input: a[] = { 16, 19, 10, 12, 18 }
Output: 31
Start from 19 and then move to 12. 

Input: a[] = {2, 5, 3, 1, 7, 3, 4}
Output: 9 
2->3->1->3

Enfoque 1: Uso de la recursividad

Básicamente una extensión de este problema.

La cuestión es que no necesitamos ir hasta el último elemento (ya que todos son números positivos, entonces podemos evitar subir al último elemento para que podamos reducir el costo).

// C++ program to find the minimum
// cost required to reach the n-th floor
#include <bits/stdc++.h>
using namespace std;
 
// function to find the minimum cost
// to reach N-th floor
 
 
int minimumCost( int n , int cost[]){
    if(n == 0) return cost[0] ;
    if(n == 1) return cost[1] ;
   
     int top = min( minimumCost(n-1,cost) + cost[n] ,
                        minimumCost(n-2, cost)+ cost[n] );
  
}
 
// Driver Code
int main()
{
    int a[] = { 16, 19, 10, 12, 18 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << minimumCost(n-2, a);
    return 0;
}

/* Java code for finding minimum cost */
import java.io.*;
 
class GFG
{
 
  // function to find minimum cost
  public static int minimumCost(int n, int cost[]){
    if(n == 0) return cost[0] ;
    if(n == 1) return cost[1] ;
 
    int top = Math.min( minimumCost(n-1,cost) + cost[n] ,
                       minimumCost(n-2, cost)+ cost[n] );
    return top;
  }
  public static void main (String[] args) {
    int a[] = { 16, 19, 10, 12, 18 };
    int n = a.length;
    System.out.println(minimumCost(n-2,a));
  }
}
 
//  This code is contributed by rchandra

31

Enfoque 2: Memoización

Podemos almacenar el resultado de la recurrencia en la array dp[]

// C++ program to find the minimum
// cost required to reach the n-th floor
#include <bits/stdc++.h>
using namespace std;
 
// function to find the minimum cost
// to reach N-th floor
int minimumCostMemoized(int n, vector<int> &cost, vector<int> &dp)
{
    if (n == 0)
        return cost[0];
    if (n == 1)
        return cost[1];
    if (dp[n] != -1)
        return dp[n];
    dp[n] = min(minimumCostMemoized(n - 1, cost, dp) + cost[n],
                minimumCostMemoized(n - 2, cost, dp) + cost[n]);
    return dp[n];
}
 
int minCostClimbingStairs(vector<int> &cost)
{
    int n = cost.size();
    vector<int> dp(n + 1, -1);
    int ans = min(minimumCostMemoized(n - 2, cost, dp), minimumCostMemoized(n - 1, cost, dp));
    return ans;
}
 
// Driver Code
int main()
{
    vector<int> a{ 16, 19, 10, 12, 18 };
    cout << minCostClimbingStairs(a);
    return 0;
}

/*package whatever //do not write package name here */
 
import java.io.*;
import java.util.Arrays;
 
class GFG {
  // function to find the minimum cost
  // to reach N-th floor
  static int minimumCostMemoized( int n,int cost[], int dp[])
  {
    // base case
    if(n == 0) return cost[0] ;
    if(n == 1) return cost[1] ;
 
    if(dp[n] != -1) return dp[n];
 
    return dp[n] = Math.min( minimumCostMemoized(n-1,cost,dp) + cost[n] ,
                            minimumCostMemoized(n-2, cost,dp)+ cost[n] );
  }
 
  static int minimumCost(int cost[], int n){
    int dp[] = new int[n];
    Arrays.fill(dp,-1);
    int top = minimumCostMemoized( n-2,cost, dp) ;
    return dp[n-2] ;
  }  
  public static void main (String[] args) {
    int a[] = { 16, 19, 10, 12, 18 };
    int n = a.length;
    System.out.println(minimumCost(a,n));
  }
}
 
// This code is contributed by rchandra.

31

Complejidad de tiempo : O(N) 

Espacio Auxiliar: O(N)

Enfoque 3: Sea dp[i] el costo de subir la i-ésima escalera desde el 0-ésimo o el 1-ésimo escalón. Por lo tanto, dp[i] = costo[i] + min(dp[i-1], dp[i-2]) . Dado que se necesitan dp[i-1] y dp[i-2] para calcular el costo de viajar desde el i-ésimo paso, se puede usar un enfoque de abajo hacia arriba para resolver el problema. La respuesta será el costo mínimo de llegar a la escalera n-1 ^y la escalera n- ² . Calcule la array dp[] de forma ascendente. 

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

// C++ program to find the minimum
// cost required to reach the n-th floor
#include <bits/stdc++.h>
using namespace std;
 
// function to find the minimum cost
// to reach N-th floor
int minimumCost(int cost[], int n)
{
    // declare an array
    int dp[n];
 
    // base case
    if (n == 1)
        return cost[0];
 
    // initially to climb till 0-th
    // or 1th stair
    dp[0] = cost[0];
    dp[1] = cost[1];
 
    // iterate for finding the cost
    for (int i = 2; i < n; i++) {
        dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
    }
 
    // return the minimum
    return min(dp[n - 2],dp[n-1]);
}
 
// Driver Code
int main()
{
    int a[] = { 16, 19, 10, 12, 18 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << minimumCost(a, n);
    return 0;
}

// Java program to find the
// minimum cost required to
// reach the n-th floor
import java.io.*;
import java.util.*;
 
class GFG
{
// function to find
// the minimum cost
// to reach N-th floor
static int minimumCost(int cost[],
                       int n)
{
    // declare an array
    int dp[] = new int[n];
 
    // base case
    if (n == 1)
        return cost[0];
 
    // initially to
    // climb till 0-th
    // or 1th stair
    dp[0] = cost[0];
    dp[1] = cost[1];
 
    // iterate for finding the cost
    for (int i = 2; i < n; i++)
    {
        dp[i] = Math.min(dp[i - 1],
                         dp[i - 2]) + cost[i];
    }
 
    // return the minimum
    return Math.min(dp[n - 2],
                    dp[n - 1]);
}
 
// Driver Code
public static void main(String args[])
{
    int a[] = { 16, 19, 10, 12, 18 };
    int n = a.length;
    System.out.print(minimumCost(a, n));
}
}

# Python3 program to find
# the minimum cost required
# to reach the n-th floor
 
# function to find the minimum
# cost to reach N-th floor
def minimumCost(cost, n):
 
    # declare an array
    dp = [None]*n
 
    # base case
    if n == 1:
        return cost[0]
 
    # initially to climb
    # till 0-th or 1th stair
    dp[0] = cost[0]
    dp[1] = cost[1]
 
    # iterate for finding the cost
    for i in range(2, n):
        dp[i] = min(dp[i - 1],
                    dp[i - 2]) + cost[i]
 
    # return the minimum
    return min(dp[n - 2], dp[n - 1])
 
# Driver Code
if __name__ == "__main__":
    a = [16, 19, 10, 12, 18 ]
    n = len(a)
    print(minimumCost(a, n))
 
# This code is contributed
# by ChitraNayal

// C# program to find the
// minimum cost required to
// reach the n-th floor
using System;
 
class GFG
{
// function to find
// the minimum cost
// to reach N-th floor
static int minimumCost(int[] cost,
                       int n)
{
    // declare an array
    int []dp = new int[n];
 
    // base case
    if (n == 1)
        return cost[0];
 
    // initially to
    // climb till 0-th
    // or 1th stair
    dp[0] = cost[0];
    dp[1] = cost[1];
 
    // iterate for finding the cost
    for (int i = 2; i < n; i++)
    {
        dp[i] = Math.Min(dp[i - 1],
                         dp[i - 2]) + cost[i];
    }
 
    // return the minimum
    return Math.Min(dp[n - 2],
                    dp[n - 1]);
}
 
// Driver Code
public static void Main()
{
    int []a = { 16, 19, 10, 12, 18 };
    int n = a.Length;
    Console.WriteLine(minimumCost(a, n));
}
}
 
// This code is contributed
// by Subhadeep

<?php
// PHP program to find the
// minimum cost required
// to reach the n-th floor
 
// function to find the minimum
// cost to reach N-th floor
function minimumCost(&$cost, $n)
{
    // declare an array
 
    // base case
    if ($n == 1)
        return $cost[0];
 
    // initially to climb
    // till 0-th or 1th stair
    $dp[0] = $cost[0];
    $dp[1] = $cost[1];
 
    // iterate for finding
    // the cost
    for ($i = 2; $i < $n; $i++)
    {
        $dp[$i] = min($dp[$i - 1],
                      $dp[$i - 2]) +
                      $cost[$i];
    }
 
    // return the minimum
    return min($dp[$n - 2],
               $dp[$n - 1]);
}
 
// Driver Code
$a = array(16, 19, 10, 12, 18);
$n = sizeof($a);
echo(minimumCost($a, $n));
     
// This code is contributed
// by Shivi_Aggarwal
?>

<script>
 
// Javascript program to find the
// minimum cost required to
// reach the n-th floor
 
     
    // function to find
// the minimum cost
// to reach N-th floor   
    function minimumCost(cost,n)
    {
        // declare an array
    let dp = new Array(n);
  
    // base case
    if (n == 1)
        return cost[0];
  
    // initially to
    // climb till 0-th
    // or 1th stair
    dp[0] = cost[0];
    dp[1] = cost[1];
  
    // iterate for finding the cost
    for (let i = 2; i < n; i++)
    {
        dp[i] = Math.min(dp[i - 1],
                         dp[i - 2]) + cost[i];
    }
  
    // return the minimum
    return Math.min(dp[n - 2],
                    dp[n - 1]);
    }
     
    // Driver Code
    let a=[16, 19, 10, 12, 18 ];
    let n = a.length;
    document.write(minimumCost(a, n));
     
 
// This code is contributed by rag2127
 
</script>

31

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

Enfoque 4 optimizado para el espacio: en lugar de usar la array dp[] para memorizar el costo, use dos variables dp1 y dp2. Dado que solo se requiere el costo de llegar a las dos últimas escaleras, use dos variables y actualícelas intercambiándolas cuando suba una escalera. 

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

// C++ program to find the minimum
// cost required to reach the n-th floor
// space-optimized solution
#include <bits/stdc++.h>
using namespace std;
 
// function to find the minimum cost
// to reach N-th floor
int minimumCost(int cost[], int n)
{
    int dp1 = 0, dp2 = 0;
 
    // traverse till N-th stair
    for (int i = 0; i < n; i++) {
        int dp0 = cost[i] + min(dp1, dp2);
 
        // update the last two stairs value
        dp2 = dp1;
        dp1 = dp0;
    }
  //dp2 gives the cost if started climbing from index 1 and dp1 from index 0
    return  min(dp2,dp1);
}
// Driver Code
int main()
{
    int a[] = { 2, 5, 3, 1, 7, 3, 4 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << minimumCost(a, n);
    return 0;
}

// Java program to find the
// minimum cost required to
// reach the n-th floor
// space-optimized solution
import java.io.*;
import java.util.*;
 
class GFG
{
// function to find
// the minimum cost
// to reach N-th floor
static int minimumCost(int cost[], int n)
{
    int dp1 = 0, dp2 = 0;
 
    // traverse till N-th stair
    for (int i = 0; i < n; i++)
    {
        int dp0 = cost[i] +
                  Math.min(dp1, dp2);
 
        // update the last
        // two stairs value
        dp2 = dp1;
        dp1 = dp0;
    }
    return Math.min(dp1, dp2);
}
 
// Driver Code
public static void main(String args[])
{
    int a[] = { 2, 5, 3, 1, 7, 3, 4 };
    int n = a.length;
    System.out.print(minimumCost(a, n));
}
}

# Python3 program to find
# the minimum cost required
# to reach the n-th floor
# space-optimized solution
 
# function to find the minimum
# cost to reach N-th floor
def minimumCost(cost, n):
 
    dp1 = 0
    dp2 = 0
 
    # traverse till N-th stair
    for i in range(n):
        dp0 = cost[i] + min(dp1, dp2)
 
        # update the last
        # two stairs value
        dp2 = dp1
        dp1 = dp0
    return min(dp1, dp2)
 
# Driver Code
if __name__ == "__main__":
    a = [ 2, 5, 3, 1, 7, 3, 4 ]
    n = len(a)
    print(minimumCost(a, n))
     
# This code is contributed
# by ChitraNayal

// C# program to find the
// minimum cost required to
// reach the n-th floor
// space-optimized solution
using System;
 
class GFG
{
// function to find
// the minimum cost
// to reach N-th floor
static int minimumCost(int[] cost,
                       int n)
{
    int dp1 = 0, dp2 = 0;
 
    // traverse till N-th stair
    for (int i = 0; i < n; i++)
    {
        int dp0 = cost[i] +
                  Math.Min(dp1, dp2);
 
        // update the last
        // two stairs value
        dp2 = dp1;
        dp1 = dp0;
    }
    return Math.Min(dp1, dp2);
}
 
// Driver Code
public static void Main()
{
    int[] a = { 2, 5, 3, 1, 7, 3, 4 };
    int n = a.Length;
    Console.Write(minimumCost(a, n));
}
}
 
// This code is contributed
// by ChitraNayal

<?php
// PHP program to find the
// minimum cost required to
// reach the n-th floor
// space-optimized solution
 
// function to find the minimum
// cost to reach N-th floor
function minimumCost(&$cost, $n)
{
    $dp1 = 0;
    $dp2 = 0;
 
    // traverse till N-th stair
    for ($i = 0; $i < $n; $i++)
    {
        $dp0 = $cost[$i] +
               min($dp1, $dp2);
 
        // update the last
        // two stairs value
        $dp2 = $dp1;
        $dp1 = $dp0;
    }
    return min($dp1, $dp2);
}
// Driver Code
$a = array(2, 5, 3, 1, 7, 3, 4);
$n = sizeof($a);
echo (minimumCost($a, $n));
 
// This code is contributed
// by Shivi_Aggarwal
?>

<script>
// Javascript program to find the
// minimum cost required to
// reach the n-th floor
// space-optimized solution
     
    // function to find
// the minimum cost
// to reach N-th floor
    function minimumCost(cost,n)
    {
        let dp1 = 0, dp2 = 0;
  
    // traverse till N-th stair
    for (let i = 0; i < n; i++)
    {
        let dp0 = cost[i] +
                  Math.min(dp1, dp2);
  
        // update the last
        // two stairs value
        dp2 = dp1;
        dp1 = dp0;
    }
    return Math.min(dp1, dp2);
    }
     
    // Driver Code
    let a=[2, 5, 3, 1, 7, 3, 4 ];
    let n = a.length;
    document.write(minimumCost(a, n));
     
 
// This code is contributed by avanitrachhadiya2155
</script>

9

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

El siguiente problema se puede resolver utilizando un enfoque de arriba hacia abajo. En ese caso la recurrencia será dp[i] = costo[i] + min(dp[i+1], dp[i+2]).