모각코 4주차 dp

198. House Robber

LeetCode - The World's Leading Online Programming Learning Platform

 

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return 0
        prev1 = 0
        prev2 = 0
        for num in nums:
            tmp = prev1
            prev1 = max(prev2 + num, prev1)
            prev2 = tmp
        return prev1

 

 

 

746. Min Cost Climbing Stairs

LeetCode - The World's Leading Online Programming Learning Platform

class Solution(object):
    def minCostClimbingStairs(self, cost):
        """
        :type cost: List[int]
        :rtype: int
        """
        step = [0] * len(cost)
        total = 0
        step[0] = cost[0]
        step[1] = cost[1]
        for i in range(2, len(cost)):
            step[i] = min(step[i-1]+cost[i], step[i-2]+cost[i])
        return  min(step[len(cost)-1], step[len(cost)-2])