LeetCode刷题笔记（五）动态规划

五. 动态规划

动态规划的两个核心要素：状态空间和状态方程。

53. 最大子序和

题目：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
输入：输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6 = [4,-1,2,1]
思考：f(i)表示第 i 个数结尾的连续子数组的最大和，那么状态转移方程为：f(i) = max{f(i-1)+nums[i], nums[i] }

    def maxSubArray(self, nums: List[int]) -> int:
        size = len(nums)
        pre = 0 # f(i-1)
        res = nums[0] # 记录输出结果
        for i in range(size):
            pre = max(nums[i], pre + nums[i])
            res = max(res, pre)
        return res

70. 爬楼梯

题目：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
思考：其实他是一个斐波那契数列问题。递归公式是climb(n) = climb(n-1)+climb(n-2)。

    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
        a, b = 1, 2
        for i in range(2, n):
            a, b = b, a+b
        return b

121. 买卖股票的最佳时机

题目：买卖股票，当天买的得明天买。
思考：参考 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/gu-piao-wen-ti-python3-c-by-z1m/

    def maxProfit(self, prices: List[int]) -> int:
        if not prices: 
            return 0
        res = 0
        profit = [[0 for i in range(3)] for i in range(len(prices))]
        profit[0][0], profit[0][1], profit[0][2] = 0, -prices[0], 0

        for i in range(1, len(prices)):
            profit[i][0] = profit[i-1][0]
            profit[i][1] = max(profit[i-1][1], profit[i-1][0]-prices[i])
            profit[i][2] = profit[i-1][1] + prices[i]
            res = max(res, profit[i][0], profit[i][1], profit[i][2])
        
        return res

122. 买卖股票的最佳时机 II

题目：买卖股票，当天可以无限次买卖。
思考：无限次买卖，不用动态规划，用贪心。有钱就挣。

    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        len_p = len(prices)
        for i in range(1, len_p):
            tmp = prices[i] - prices[i-1] # 两天价差为正，就买卖一轮挣差价
            if tmp >= 0:
                res += tmp
        return res