Min Cost Climbing Stairs

🏠 ⬅️ ➡️

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Example 1:

Input: cost = [10,15,20] Output: 15 Explanation: You will start at index 1. - Pay 15 and climb two steps to reach the top. The total cost is 15.

Example 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1] Output: 6 Explanation: You will start at index 0. - Pay 1 and climb two steps to reach index 2. - Pay 1 and climb two steps to reach index 4. - Pay 1 and climb two steps to reach index 6. - Pay 1 and climb one step to reach index 7. - Pay 1 and climb two steps to reach index 9. - Pay 1 and climb one step to reach the top. The total cost is 6.

Constraints:

  • 2 <= cost.length <= 1000
  • 0 <= cost[i] <= 999
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 3 ! number of steps
    integer, dimension(n) :: cost = (/ 10, 15, 20 /) ! cost of each step
    integer :: i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z
    integer :: min_cost

    ! solve the problem
    min_cost = solve(cost)

    ! print the solution
    write (*, '(A, I0)') 'Minimum cost: ', min_cost

contains

    function solve(cost) result(min_cost)
        implicit none
        integer, intent(in) :: cost(:)
        integer :: min_cost
        integer :: i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z

        min_cost = huge(1_8) ! initialize with a large value

        do i = 1, size(cost) - 1
            do j = i + 1, size(cost)
                if (cost(i) + cost(j) < min_cost) then
                    min_cost = cost(i) + cost(j)
                end if
            end do
        end do

    end function solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module MinCostClimbingStairs
    implicit none
    private
    public :: minCostClimbingStairs
contains
    function minCostClimbingStairs(cost) result(minCost)
        integer, intent(in) :: cost(:)
        integer :: minCost
        integer :: dp(size(cost))
        integer :: i

        ! Initialize the dynamic programming array
        dp(1) = cost(1)
        dp(2) = cost(2)

        ! Loop through the remaining steps
        do i = 3, size(cost)
            dp(i) = min(dp(i-1), dp(i-2)) + cost(i)
        end do

        ! Return the minimum cost
        minCost = min(dp(size(cost)-1), dp(size(cost)))
    end function minCostClimbingStairs
end module MinCostClimbingStairs

program test_minCostClimbingStairs
    use MinCostClimbingStairs
    implicit none
    integer, parameter :: cost(3) = [10, 15, 20]
    integer, parameter :: cost2(10) = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
    integer :: minCost

    ! Test case 1
    minCost = minCostClimbingStairs(cost)
    write (*,*) "Min cost: ", minCost

    ! Test case 2
    minCost = minCostClimbingStairs(cost2)
    write (*,*) "Min cost: ", minCost
end program test_minCostClimbingStairs
🌐 Data from online sources 
class WordFilter:

    def __init__(self, words):
        self.dict = {}
        for i, word in enumerate(words):
            for j in range(len(word) + 1):
                self.dict[word[:j] + "#" + word[j:]] = i

    def f(self, prefix, suffix):
        return self.dict.get(prefix + "#" + suffix, -1)

1. We create a hash table called `dict`.
  1. For every word in the given words list, we iterate through each character position in the word.
  2. For each position, we create a new string that combines the word's prefix (characters before the position) and suffix (characters after the position), with a '#' as a separator. This new string is added to the dict hash table with the corresponding index of the word in the list as its value.
  3. When the f function is called with a given prefix and suffix, we search for the combined string (prefix + '#' + suffix) in the dict. If it exists, we return the index value stored for that string, otherwise we return -1.
🌐 Data from online sources 
#include <unordered_map>
#include <string>
using namespace std;

class WordFilter {
    unordered_map<string, int> dict;
public:
    WordFilter(vector<string>& words) {
        for (int i = 0; i < words.size(); ++i) {
            for (int j = 0; j <= words[i].size(); ++j) {
                dict[words[i].substr(0, j) + "#" + words[i].substr(j)] = i;
            }
        }
    }

    int f(string prefix, string suffix) {
        auto it = dict.find(prefix + "#" + suffix);
        if (it == dict.end()) {
            return -1;
        }
        return it->second;
    }
};

1. We create a hash table called `dict`.
  1. For every word in the given words list, we iterate through each character position in the word.
  2. For each position, we create a new string that combines the word's prefix (characters before the position) and suffix (characters after the position), with a '#' as a separator. This new string is added to the dict hash table with the corresponding index of the word in the list as its value.
  3. When the f function is called with a given prefix and suffix, we search for the combined string (prefix + '#' + suffix) in the dict. If it exists, we return the index value stored for that string, otherwise we return -1.