2022-02-19 动态规划专题

动态规划问题基本解题步骤

1. 设计状态
2. 写出状态转移方程
3. 设置初始状态
4. 处理非法状态
5. 执行状态转移
6. 后处理
7. 返回最终结果

显式转移方程

• 斐波那契数列
• 阶乘

隐式转移方程

• 爬楼梯
• 爬楼梯最小花费

注意：对于隐式状态转移方程，可以先从初始的几个状态列举出来，看能不能看出规律

相关题目练习

剑指 Offer 10- I. 斐波那契数列

一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：1

示例 2：

输入：n = 5
输出：5

提示：

0 <= n <= 100

题解：

class Solution:
    def fib(self, n: int) -> int:
        n = n % 1000000007
        a = 0
        if n == 0:
            return a
        b = 1    
        if n == 1:
            return b
        
        sum = 0
        for i in range(2, n+1):
            sum = a + b
            a = b
            b =sum
        return sum % 1000000007

70. 爬楼梯

新解法：爬楼梯到当前台阶只能从前一阶台阶或前两阶台阶上来：F(n) = F(n - 1) + F(n - 2)

class Solution:
    def climbStairs(self, n: int) -> int:
        init0 = 1
        init1 = 1
        if n <= 1:
            return 1
        for i in range(n - 1):
            ans = init1 + init0
            init0 = init1
            init1 = ans
        return ans

746. 使用最小花费爬楼梯

题解：

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp1 = 0
        dp2 = 0
        for i in range(2, len(cost)+1):
            dp = min(dp1 + cost[i-1], dp2 + cost[i-2])
            dp2 = dp1
            dp1 = dp

        return dp1

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104

分析：

• 状态：dp[i] : 以第i个数结尾的子数组
• 状态转移：
  • 第i-1个数结尾的子数组加上第i个数
  • 第i个数单独作为子数组
  • dp[i] = max{dp[i - 1] + num[i], num[i]}
• 初始状态dp[0] = num[0]
• 最后执行状态，再所有状态中取dp最大的状态作为结果返回

题解：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        l = len(nums)
        dp = [0] * l  
        dp[0] = nums[0]
        for i in range(1, l):
            dp[i] = max(dp[i-1] + nums[i], nums[i])
        return max(dp)

优化空间：在上述的状态转移中，我们需要一个和原始数组一样大的数组存储状态，但最终我们只需要这些状态中的最大值，既然只需要最大值，那我我们只需要一个空间存最大值，一个空间取遍历就好了

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = nums[0]
        sum = nums[0]
        for i in range(1, len(nums)):
            sum = max(sum + nums[i], nums[i])
            if sum > ans:
                ans = sum

        return ans

198. 打家劫舍

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

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

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 400

分析：

• 确定状态：dp[i]：判断偷第i家的状态
• 状态转移：
  • 对于dp[i]这个状态，要么偷了第i家，收益是nums[i] + dp[i-2]
  • 要么没有偷第i家，收益是偷上一家的dp[i-1]
  • dp[i] = max(nums[i] + dp[i-2], dp[i-1])
• 初始状态：
  • 只有一家：dp[0] = nums[0]，即这家收益
  • 只有两家：dp[1] = max(nums[0], nums[1])，即偷收益多的那家
• 执行状态，最后一次偷的即最高金额

题解：

class Solution:
    def rob(self, nums: List[int]) -> int:
        l = len(nums)
        if l <= 2:
            return max(nums)

        dp = [0] * l

        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for i in range(2, l):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])

        return dp[-1]

空间优化：与上一题类似，对于求最大部分。如果用的是数组可以用两个变量优化空间

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0: return 0
        dp = [0]*n

        dp2 = 0
        dp1 = 0

        for i in range(0, n):
            dp = max(dp2 + nums[i], dp1)
            dp2 = dp1
            dp1 = dp;
        return dp1

总结：对于出现求最大值需要对此敏感，如果最大值针对一个数组状态，便可以考虑优化为两个变量代替，让空间复杂度由O(n)->O(1)

740. 删除并获得点数

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

示例 1：

输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。

示例 2：

输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。

提示：

1 <= nums.length <= 2 * 104
1 <= nums[i] <= 104

分析：转化为打家劫舍问题，只不过这次不是根据数组下标决定状态数，而是根据数组中可能取到的最大值作为状态数目。
题解：

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:

        cnt = [0] * 10001

        for n in nums:
            cnt[n] += 1

        dp1 = 0
        dp2 = 0

        for i in range(0, len(cnt)):
            dp = max(dp2 + i * cnt[i], dp1)
            dp2 = dp1
            dp1 = dp

        return dp1

121. 买卖股票的最佳时机

题解：
方法一：转化为求最大连续字串和问题

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        l = len(prices)
        new = [0] * l
        for i in range(1, l):
            new[i] = prices[i] - prices[i-1]

        init = new[0]
        ans = 0 
        for i in range(1, l):
            init = max(init + new[i], new[i])
            ans = max(ans, init)

        return ans

方法二：前缀最值角度

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        l = len(prices)
        prev_min = [0] * l
        prev_min[0] = prices[0]

        ans = 0

        for i in range(1, l):
            prev_min[i] = min(prev_min[i-1], prices[i])

            ans = max(ans, prices[i] - prev_min[i])

        return ans

1014. 最佳观光组合

给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。

一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。

返回一对观光景点能取得的最高分。

示例 1：

输入：values = [8,1,5,2,6]
输出：11
解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11

示例 2：

输入：values = [1,2]
输出：2

提示：

2 <= values.length <= 5 * 104
1 <= values[i] <= 1000

题解：
方法一：将最优化目标拆成i和j的部分，再一次循环中j部分是固定的，我们只需要j前value[i] + i的最大项提前存起来即可。注意这里不能循环求解value[i] + i，否则就是暴力穷举了，时间复杂度不满足要求

class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        l = len(values)
        maxnum = 0
        left = values[0]
        for i in range(1, l):
            maxnum = max(values[i] - i + left, maxnum)
            left = max(values[i] + i, left)

        return maxnum

方法二： 状态转移：假设我们已知前一个节点 j 能组成的最大的组合为（i，j）， 那么紧接着的一个节点 j+1 最大得分的组合一定是（i，j+1）和（j，j+1）这两个组合中较大的一个。

class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        l = len(values)
        dp = [0] * l
        dp[0] = values[0]
        dp[1] = values[1] + values[0] - 1
        for i in range(2, l):
            dp[i] = max(values[i] + values[i-1] - 1, dp[i-1] + values[i] - values[i-1] - 1)

        return max(dp)

注意：对于抽象的问题要善于总结当前状态与上一个状态的联系

1299. 将每个元素替换为右侧最大元素

给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。

完成所有替换操作后，请你返回这个数组。

示例 1：

输入：arr = [17,18,5,4,6,1]
输出：[18,6,6,6,1,-1]
解释：
- 下标 0 的元素 --> 右侧最大元素是下标 1 的元素 (18)
- 下标 1 的元素 --> 右侧最大元素是下标 4 的元素 (6)
- 下标 2 的元素 --> 右侧最大元素是下标 4 的元素 (6)
- 下标 3 的元素 --> 右侧最大元素是下标 4 的元素 (6)
- 下标 4 的元素 --> 右侧最大元素是下标 5 的元素 (1)
- 下标 5 的元素 --> 右侧没有其他元素，替换为 -1

示例 2：

输入：arr = [400]
输出：[-1]
解释：下标 0 的元素右侧没有其他元素。

提示：

1 <= arr.length <= 104
1 <= arr[i] <= 105

题解：后缀最值问题

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        l = len(arr)
        if l <= 1:
            return [-1]

        dp = [0] * l
        dp[-1] = -1
        for i in range(l-2, -1, -1):
            dp[i] = max(dp[i+1], arr[i+1])

        return dp