746 Min Cost Climbing Stairs¶

:::tip Problem can be solved using:

dynamic programming
recursive

There is a staircase, you need to pay cost[i] to leave the i floor, and you can climb 1 or 2 floors each time. Ask how much you spend at least to reach the top floor. :::

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

Example 1:

Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.

Example 2:

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

Note: cost will have a length in the range [2, 1000]. Every cost[i] will be an integer in the range [0, 999].

C# Solution¶

using System;
using System.Collections.Generic;

namespace Algorithms.Simple
{
  public class MinCostClimbingStairs
  {
    public static int Find(int[] vs)
    {
      var dp = new int[vs.Length];
      dp[0] = vs[0];
      dp[1] = vs[1];

      for (var i = 2; i < vs.Length; i++)
      {
        dp[i] = vs[i] + Math.Min(dp[i - 1], dp[i - 2]);
      }

      return Math.Min(dp[vs.Length - 1], dp[vs.Length - 2]);
    }
  }
}

C# Tests¶

using Algorithms.Simple;
using Xunit;

namespace AlgorithmTests.Simple
{
  public class MinCostClimbingStairsTests
  {
    [Fact]
    public void MinCostTest1()
    {
      Assert.Equal(15, MinCostClimbingStairs.Find(new int[] { 10, 15, 20 }));
    }

    [Fact]
    public void MinCostTest2()
    {
      Assert.Equal(6, MinCostClimbingStairs.Find(new int[] { 1, 100, 1, 1, 1, 100, 1, 1, 100, 1 }));
    }
  }
}

With O(1) Space¶

using System;
using System.Collections.Generic;

namespace Algorithms.Simple
{
  public class MinCostClimbingStairsO1Space
  {
    public static int Find(int[] vs)
    {
      int dp1 = 0;
      int dp2 = 0;

      for (var i = 2; i <= vs.Length; i++)
      {
        int dp = Math.Min(dp1 + vs[i - 1], dp2 + vs[i - 2]);
        dp2 = dp1;
        dp1 = dp;
      }

      return dp1;
    }
  }
}

C# Tests for O(1)¶

using Algorithms.Simple;
using Xunit;

namespace AlgorithmTests.Simple
{
  public class MinCostClimbingStairsO1SpaceTests
  {
    [Fact]
    public void MinCostTest1()
    {
      Assert.Equal(15, MinCostClimbingStairsO1Space.Find(new int[] { 10, 15, 20 }));
    }

    [Fact]
    public void MinCostTest2()
    {
      Assert.Equal(6, MinCostClimbingStairsO1Space.Find(new int[] { 1, 100, 1, 1, 1, 100, 1, 1, 100, 1 }));
    }
  }
}