目录

Leetcode动态规划简单题目合集

题记

刷一下动态规划的简单题,一共也没几道。顺便把前100道题里面的中等难度的动态规划题刷了。

第53、121、198是简单题。

题目

53 最大子序和

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

题解

定义状态转移方程image-20200917155253852

f(i)表示以i结尾的子串连续子数组的最大和,最后的答案应当是image-20200917155358075

一开始的想法是定义f(i)是数组前i个数中连续子数组的的最大和,但是发现写不出来转移方程。

代码

1
2
3
4
5
6
7
8
9
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        a = nums[0]
        result = nums[0]
        for i in range(1, len(nums)):
            a = max(a+nums[i], nums[i])
            result = max(result, a)

        return result

121 买卖股票的最佳时机

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。

注意:你不能在买入股票前卖出股票。

题解

状态转移方程,可以看到前i天:image-20200917142521944

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0
        a = 0
        min_price = prices[0]
        for i in range(1, len(prices)):
            a = max(a, prices[i] - min_price)
            if prices[i] < min_price:
                min_price = prices[i]
        return a

198 打家劫舍

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组,计算你不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

题解

dp 方程为:dp[i] = max(dp[i-2]+nums[i], dp[i-1])

一开始想的很复杂,分享一下心路历程: dp[i] 分3种情况 1. i-1偷了,i只能不偷,那么dp[i]=dp[i-1],并且要维护一个变量说明i没有偷; 2. i-1没偷,那么可以选择偷i,则有dp[i]=dp[i-1]+nums[i],维护一个状态说明偷了i;3. i-1没偷, i仍然选择不偷,则有dp[i] = dp[i-1],维护一个状态表示i没偷。

这是一开始的分析,显然很复杂,而且如果i-1没偷,那么就一定要偷i才能利益最大化,之所以考虑不偷,是为了让i+1能够偷。真正的思路就是2种情况:1. 偷前k-2个房子,并且偷最后一间 2. 偷前k-1个房子,不偷最后一间。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        elif len(nums) == 1:
            return nums[0]
        a,b = nums[0], max(nums[0],nums[1])
        for i in range(2, len(nums)):
            tmp = b
            b = max(a+nums[i], b)
            a = tmp
        return b