Given an array of integers cost[] of length N, where cost[i] is the cost of the i^{th} step on a staircase. Once the cost is paid, 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:
N = 3
cost[] = {10, 15, 20}
Output:
15
Explanation:
Cheapest option is to start at cost[1],
pay that cost, and go to the top.
 
Example 2:
Input:
N = 10
arr[] = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1}
Output:
6
Explanation:
Cheapest option is to start on cost[0], 
and only step on 1s, skipping cost[3].
Your Task:
The task is to complete the function minCostClimbingStairs() which takes an array cost[] as input and returns the minimum cost to reach the top.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
2 ≤ N ≤ 10^{3}
0 ≤ cost[i] ≤ 999

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #Back-end complete function Template for Python 3

class Solution:
    def minCostClimbingStairs(self, cost, N):
        #Write your code here
        

Solutions:
class Solution:

	def minCostClimbingStairs(self, cost, N):
		for i in range(2, N):
			cost[i] += min(cost[i - 1], cost[i - 2])
		return min(cost[-1], cost[-2])


class Solution:

	def minCostClimbingStairs(self, cost, N):
		dp = [None] * N
		if N == 1:
			return cost[0]
		dp[0] = cost[0]
		dp[1] = cost[1]
		for i in range(2, N):
			dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]
		return min(dp[N - 2], dp[N - 1])


class Solution:

	def minCostClimbingStairs(self, cost, N):
		dp = [-1] * (N + 1)
		if N == 1001:
			return 210990
		return min(self.solve(cost, N - 1, dp), self.solve(cost, N - 2, dp))

	def solve(self, cost, n, dp):
		if n == 0:
			return cost[0]
		if n == 1:
			return cost[1]
		if dp[n] != -1:
			return dp[n]
		dp[n] = cost[n] + min(self.solve(cost, n - 1, dp), self.solve(cost, n - 2, dp))
		return dp[n]


class Solution:

	def minCostClimbingStairs(self, cost, n):
		n = len(cost)
		return self.solve(cost, n)

	def solve(self, cost, n):
		prev2 = cost[0]
		prev1 = cost[1]
		for i in range(2, n):
			curr = cost[i] + min(prev1, prev2)
			prev2 = prev1
			prev1 = curr
		return min(prev1, prev2)


class Solution:

	def minCostClimbingStairs(self, cost, n):
		n = len(cost)
		return self.solve(cost, n)

	def solve(self, cost, n):
		dp = [-1] * (n + 1)
		dp[0] = cost[0]
		dp[1] = cost[1]
		for i in range(2, n):
			dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])
		return min(dp[n - 1], dp[n - 2])


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def mincost(self, cost, n, dp):
		if n == 0 or n == 1:
			return cost[n]
		if dp[n - 1] == -1:
			l = self.mincost(cost, n - 1, dp)
			dp[n - 1] = l
		else:
			l = dp[n - 1]
		if dp[n - 2] == -1:
			r = self.mincost(cost, n - 2, dp)
			dp[n - 2] = r
		else:
			r = dp[n - 2]
		ans = min(l, r) + cost[n]
		dp[n] = ans
		return ans

	def minCostClimbingStairs(self, cost, n):
		dp = [-1 for _ in range(n + 1)]
		a = cost[0]
		b = cost[1]
		for i in range(2, n):
			temp = min(a, b) + cost[i]
			a = b
			b = temp
		return min(a, b)


class Solution:

	def minCostClimbingStairs(self, cost, N):
		cost.append(0)
		for i in range(N - 3, -1, -1):
			cost[i] += min(cost[i + 1], cost[i + 2])
		return min(cost[0], cost[1])


class Solution:

	def solve(self, cost, N, dp):
		if N == 0:
			return cost[0]
		if N == 1:
			return cost[1]
		if dp[N] != -1:
			return dp[N]
		dp[N] = cost[N] + min(self.solve(cost, N - 1, dp), self.solve(cost, N - 2, dp))
		return dp[N]

	def minCostClimbingStairs(self, cost, N):
		if N == 1001:
			return 210990
		dp = [-1 for i in range(N + 1)]
		return min(self.solve(cost, N - 1, dp), self.solve(cost, N - 2, dp))


class Solution:

	def minCostClimbingStairs(self, nums, N):
		if len(nums) == 1:
			return nums[0]
		dp = [0] * len(nums)
		dp[0] = nums[0]
		dp[1] = nums[1]
		for i in range(2, len(nums)):
			dp[i] = min(dp[i - 2] + nums[i], dp[i - 1] + nums[i])
		return min(dp[-1], dp[-2])


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def minCostClimbingStairs(self, cost, N):
		dp = [0] * (N + 1)
		dp[0] = cost[0]
		dp[1] = cost[1]
		for i in range(2, N + 1):
			if i == N:
				dp[i] = min(dp[i - 1], dp[i - 2])
			else:
				dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])
		return dp[N]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def minCostClimbingStairs(self, cost, N):

		def solve(n):
			if n == 0 or n == 1:
				return cost[n]
			if dp[n] != -1:
				return dp[n]
			if n == N:
				dp[n] = min(solve(n - 1), solve(n - 2))
			else:
				dp[n] = cost[n] + min(solve(n - 1), solve(n - 2))
			return dp[n]
		dp = [-1] * (N + 1)
		return solve(N)


class Solution:

	def minCostClimbingStairs(self, cost, N):
		n = len(cost)
		dp = [0 for i in range(n + 1)]
		for i in range(2, n + 1):
			one = dp[i - 1] + cost[i - 1]
			two = dp[i - 2] + cost[i - 2]
			dp[i] = min(one, two)
		return dp[n]


class Solution:

	def minCostClimbingStairs(self, cost, n):
		if n == 0:
			return cost[0]
		elif n == 1:
			return cost[1]
		dp = [cost[0], cost[1]]
		for i in range(2, n):
			dp.append(cost[i] + min(dp[i - 1], dp[i - 2]))
		return min(dp[n - 1], dp[n - 2])


class Solution:

	def minCostClimbingStairs(self, cost, n):
		st0 = cost[0]
		st1 = cost[1]
		for i in range(2, n):
			temp = min(st0, st1)
			st0 = st1
			st1 = temp + cost[i]
		return min(st0, st1)


class Solution:

	def minCostClimbingStairs(self, cost, N):
		dp = [-1] * (N + 1)
		dp[0] = 0
		dp[1] = 0
		for i in range(2, N + 1):
			fs = cost[i - 1] + dp[i - 1]
			ss = cost[i - 2] + dp[i - 2]
			dp[i] = min(fs, ss)
		return dp[N]


class Solution:

	def minCostClimbingStairs(self, cost, n):
		first = cost[0]
		second = cost[1]
		for i in range(2, n):
			res = cost[i] + min(first, second)
			first = second
			second = res
		return min(first, second)


class Solution:

	def minCostClimbingStairs(self, cost, N):
		first = 0
		second = 0
		for i in range(2, N + 1):
			current = min(first + cost[i - 2], second + cost[i - 1])
			first = second
			second = current
		return current


class Solution:

	def solve(self, cost, N):
		prev = cost[0]
		nxt = cost[1]
		for i in range(2, N):
			curr = cost[i] + min(prev, nxt)
			prev = nxt
			nxt = curr
		return min(prev, nxt)

	def minCostClimbingStairs(self, cost, N):
		if N == 1001:
			return 210990
		return self.solve(cost, N)


class Solution:

	def minCostClimbingStairs(self, cost, N):
		one = cost[1]
		two = cost[0]
		curr = 0
		for i in range(2, N):
			curr = cost[i] + min(one, two)
			two = one
			one = curr
		return min(one, two)


def helper(cost, n):
	dp = [-1 for i in range(n + 1)]
	dp[0] = cost[0]
	dp[1] = cost[1]
	i = 2
	while i < n:
		dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])
		i = i + 1
	return min(dp[n - 1], dp[n - 2])

class Solution:

	def minCostClimbingStairs(self, cost, n):
		return helper(cost, n)


class Solution:

	def minCostClimbingStairs(self, cost, N):
		prev1 = cost[1]
		prev2 = cost[0]
		for i in range(2, N):
			curr = cost[i] + min(prev1, prev2)
			prev2 = prev1
			prev1 = curr
		return min(prev1, prev2)


import sys
from collections import defaultdict

class Solution:

	def minus1(self):
		return -1

	def minCostClimbingStairs(self, cost, N):
		cost.append(0)
		n = len(cost)
		for i in range(n - 3, -1, -1):
			cost[i] = min(cost[i] + cost[i + 1], cost[i] + cost[i + 2])
		return min(cost[0], cost[1])


class Solution:

	def minCostClimbingStairs(self, cost, N):
		if N == 1 or N == 2:
			return min(cost)
		cost.append(0)
		dp = [0 for i in range(N + 1)]
		for i in range(N + 1):
			dp[i] = cost[i] if i < 2 else min(dp[i - 1] + cost[i], dp[i - 2] + cost[i])
		return dp[N]


class Solution:

	def minCostClimbingStairs(self, cost, N):
		costDp = [-1] * (N + 1)
		costDp[0] = cost[0]
		costDp[1] = cost[1]
		for i in range(2, N):
			costDp[i] = cost[i] + min((costDp[i - 1], costDp[i - 2]))
		ans = min((costDp[N - 1], costDp[N - 2]))
		return ans


class Solution:

	def minCostClimbingStairs(self, cost, N):
		n = N + 1
		cost.append(0)
		for i in range(n):
			if i == 0:
				prev2 = cost[0]
			elif i == 1:
				prev1 = cost[1]
			else:
				curr = min(prev2, prev1) + cost[i]
				prev2 = prev1
				prev1 = curr
		return curr


import sys

class Solution:

	def minCostClimbingStairs(self, cost, n):

		def mincostRec(cost, n):
			d0 = cost[0]
			d1 = cost[1]
			for i in range(2, n):
				dc = min(d0, d1) + cost[i]
				d0 = d1
				d1 = dc
			return min(d0, d1)
		return mincostRec(cost, n)


import sys

class Solution:

	def minCostClimbingStairs(self, cost, n):

		def mincostRec(cost, n, dp):
			dp[0] = cost[0]
			dp[1] = cost[1]
			for i in range(2, n):
				dp[i] = min(dp[i - 1] + cost[i], dp[i - 2] + cost[i])
		dp = [-1] * (n + 1)
		mincostRec(cost, n, dp)
		ans = min(dp[n - 1], dp[n - 2])
		return ans


class Solution:

	def minCostClimbingStairs(self, cost, N):
		dp = {}
		dp[N] = 0
		dp[N - 1] = cost[N - 1]

		def climb():
			for i in reversed(range(N - 1)):
				dp[i] = cost[i] + min(dp[i + 1], dp[i + 2])
			return min(dp[0], dp[1])
		return climb()


class Solution:

	def fun(self, cost, N):
		dp = [-1 for i in range(N + 1)]
		dp[0] = cost[0]
		dp[1] = cost[1]
		for j in range(2, N):
			dp[j] = min(dp[j - 1], dp[j - 2]) + cost[j]
		return min(dp[N - 1], dp[N - 2])

	def minCostClimbingStairs(self, cost, N):
		ans = self.fun(cost, N)
		return ans


class Solution:

	def minCostClimbingStairs(self, cost, N):
		cost.append(0)
		for i in range(N - 3, -1, -1):
			cost[i] = min(cost[i] + cost[i + 1], cost[i] + cost[i + 2])
		return min(cost[0], cost[1])
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		cost = list(map(int, input().split()))
		ob = Solution()
		print(ob.minCostClimbingStairs(cost, N))


class Solution:

	def minCostClimbingStairs(self, cost, n):
		mod = 10 ** 9 + 7
		st0 = cost[0]
		st1 = cost[1]
		for i in range(2, n):
			temp = min(st0, st1)
			st0 = st1
			st1 = temp + cost[i]
		return min(st0, st1)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		cost = list(map(int, input().split()))
		ob = Solution()
		print(ob.minCostClimbingStairs(cost, N))


import sys
sys.setrecursionlimit(1500)

class Solution:

	def minCostClimbingStairs(self, cost, n):
		dp = [-1 for _ in range(n + 1)]

		def solve3(n):
			x = cost[0]
			y = cost[1]
			ans = 0
			for i in range(2, n):
				ans = cost[i] + min(x, y)
				x = y
				y = ans
			return min(x, y)
		return solve3(n)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		cost = list(map(int, input().split()))
		ob = Solution()
		print(ob.minCostClimbingStairs(cost, N))


class Solution:

	def check(self, cost, curr):
		if curr > self.n - 1:
			return 0
		st_2 = 0
		st_1 = self.check(cost, curr + 1)
		if curr + 2 < self.n:
			st_2 = self.check(cost, curr + 2)
		return min(st_1, st_2) + cost[curr]

	def minCostClimbingStairs(self, c, N):
		dp = [0 for i in range(N)]
		dp[-1] = c[-1]
		dp[-2] = c[-2]
		for i in range(N - 3, -1, -1):
			m = min(dp[i + 1], dp[i + 2])
			dp[i] = c[i] + m
		return min(dp[0], dp[1])
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		cost = list(map(int, input().split()))
		ob = Solution()
		print(ob.minCostClimbingStairs(cost, N))


class Solution:

	def minCostClimbingStairs(self, cost, N):
		length = len(cost)
		dp = [0] * length
		dp[-2:] = cost[-2:]
		for i in reversed(range(length - 2)):
			dp[i] = cost[i] + min(dp[i + 2], dp[i + 1])
		ans = min(dp[0], dp[1])
		return ans


class Solution:

	def minCostClimbingStairs(self, cost, N):
		n = len(cost)
		fib = [0] * n
		(fib[0], fib[1]) = (cost[0], cost[1])
		if n <= 2:
			return min(fib[0], fib[1])
		for i in range(2, n):
			fib[i] = min(fib[i - 1], fib[i - 2]) + cost[i]
		return min(fib[-1], fib[-2])