开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> LeetCode Cookbook 动态规划（精华） -> 正文阅读

[数据结构与算法]LeetCode Cookbook 动态规划（精华）

CSDN话题挑战赛第2期
参赛话题：算法题解

LeetCode Cookbook 动态规划（精华）

?? 本节内容主要是一些零散的题目，主要是关于子树、叶子结点的问题。

70. 爬楼梯（model-I 加）

题目链接：70. 爬楼梯
题目大意：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

例如：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

解题思路：斐波那契数
时间复杂度： $O (N)$ N为循环次数
空间复杂度： $O (N)$

class Solution:
    def climbStairs(self, n: int) -> int:
        
        # 好理解的数组
        dp = [0] * (n+1)
        dp[0]=dp[1]=1
        for i in range(2,n+1):
            dp[i] = dp[i-1]+dp[i-2]
        return dp[-1]

174. 地下城游戏（model-II 路径选择）

题目链接：174. 地下城游戏
题目大意：一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快到达公主，骑士决定每次只向右或向下移动一步。
编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。
例如，考虑到如下布局的地下城，如果骑士遵循最佳路径右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。
在这里插入图片描述

说明:
骑士的健康点数没有上限。
任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

解题思路：倒着来,从目标地出发,前往初始点,注意血量问题,最少为1才可以前进。

时间复杂度： $O (M \times N)$ 给定矩阵M行N列
空间复杂度： $O (M \times N)$

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        m,n = len(dungeon),len(dungeon[0])
        dp = [[10**9]*(n+1) for _ in range(m+1)]
        dp[m][n-1] = dp[m-1][n] = 1
        for i in range(m-1,-1,-1):
            for j in range(n-1,-1,-1):
                # 两个方向 选一个小的即可
                minn = min(dp[i+1][j],dp[i][j+1])
                dp[i][j] = max(minn-dungeon[i][j],1)
        return dp[0][0]

198. 打家劫舍（model-II 路径选择）

题目链接：198. 打家劫舍
题目大意：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

例如：

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

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

解题思路：相隔路径与相邻路径的择优选择.
时间复杂度： $O (N)$ N为数组长度
空间复杂度： $O (N)$

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

123. 买卖股票的最佳时机 III（model-III 股票）

题目链接：123. 买卖股票的最佳时机 III
题目大意：给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

例如：

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

输入：prices = [7,6,4,3,1] 
输出：0 
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

解题思路：这题真有意思,典型的动态规划题目,因为最多做两笔买卖,所以 dp 设置4个位置就行.
时间复杂度： $O (N)$ N为数组长度
空间复杂度： $O (1)$

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n==0: return 0
        # 一共就两笔交易
        dp = [0]*4
        # 定义 0,2 买入 1,3卖出
        # 两笔可以只做一笔
        dp[0] = dp[2] = -prices[0]
        for i in range(1,n):
            dp[0] = max(dp[0],-prices[i])
            dp[1] = max(dp[1],dp[0]+prices[i])
            dp[2] = max(dp[2],dp[1]-prices[i])
            dp[3] = max(dp[3],dp[2]+prices[i])
        return dp[-1]

309. 最佳买卖股票时机含冷冻期（model-VI 二叉搜索树）

题目链接：309. 最佳买卖股票时机含冷冻期
题目大意：给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格。?
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

例如：

输入: prices = [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

输入: prices = [1]
输出: 0

解题思路: 建立三种状态:状态1：手上持有的股票买入状态的最大收益; 状态2：卖出状态1 手上没有股票处于冷冻期的最大收益; 状态3：卖出状态2 手上没有股票已经渡过冷冻期的最大收益.
时间复杂度： $O (N)$ N为数组长度
空间复杂度： $O (N)$

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n == 0: return 0
        dp = [[0] * 3 for _ in range(n)]
        dp[0][0] = -prices[0]
        for i in range(1,n):
            # 状态1：手上持有的股票 买入状态的最大收益
            # 状态2：卖出状态1 手上没有股票 处于冷冻期的最大收益
            # 状态3：卖出状态2 手上没有股票 已经渡过冷冻期的最大收益
            # 买入 减 ；卖出 加
            dp[i][0] = max(dp[i-1][0],dp[i-1][2]-prices[i])
            dp[i][1] = dp[i-1][0]+prices[i]
            dp[i][2] = max(dp[i-1][1],dp[i-1][2])
        print(dp)
        return max(dp[n-1][1],dp[n-1][2])

322. 零钱兑换（model-VIII 背包）

题目链接：322. 零钱兑换
题目大意：给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。

例如：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

输入：coins = [2], amount = 3
输出：-1

输入：coins = [1], amount = 0
输出：0

解题思路：背包问题找准状态转移方程
时间复杂度： $O (S \times N)$ S为金额,N为面额个数
空间复杂度： $O (S)$

class Solution:
    def coinChange(self, coins: List[int], n: int) -> int:
        if n == 0: return 0
        # 状态转移方程 F(i) = min F(i-cj) +1 其中 j = 0,...,n-1
        dp = [float('inf')] * (n+1)
        dp[0] = 0
        for cj in coins:
            for x in range(cj,n+1):
                dp[x] = min(dp[x],dp[x-cj]+1)
        return dp[n] if dp[n] != float('inf') else -1

416. 分割等和子集（model-VIII 背包）

题目链接： 416. 分割等和子集
题目大意：给你一个只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

例如：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

解题思路：01背包倒序遍历
时间复杂度： $O (T \times N)$ T为程序中的tSum,N为数组长度
空间复杂度： $O (T)$

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        nSum = sum(nums)
        if nSum%2: return False
        t = nSum//2
        dp = [False]*(t+1)
        dp[0] = True
        n = len(nums)
        for num in nums:
            for j in range(t,num-1,-1):
                dp[j] = dp[j] or dp[j-num]
        return dp[t]

474. 一和零（model-VIII 背包）

题目链接：474. 一和零
题目大意：给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

例如：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2

解题思路：二维背包问题
时间复杂度： $O (l \times m \times n + L)$ l为数组strs的长度;L为数组str所有字符长度之和 m,n分别为0和1的容量
空间复杂度： $O (m \times n)$

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0]*(n+1) for _ in range(m+1)] 
        # 遍历物品
        for ch in strs:
            ones,zeros = ch.count('1'),ch.count('0')
            # 倒序遍历背包容量
            for i in range(m,zeros-1,-1):
                for j in range(n,ones-1,-1):
                    dp[i][j] = max(dp[i][j],dp[i-zeros][j-ones]+1)
        return dp[m][n]

1049. 最后一块石头的重量 II（model-VIII 背包）

题目链接：1049. 最后一块石头的重量 II
题目大意：有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

例如：

输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

输入：stones = [31,26,33,21,40]
输出：5

解题思路：背包问题找寻最接近总和一半的背包
时间复杂度： $O (N \times S)$ N为数组长度,S为数组所有元素之和
空间复杂度： $O (S)$

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        tS = sum(stones)
        t = tS//2
        # 30*100//2 提示的范围
        dp = [0]*15001
        n = len(stones)
        for i in range(n):
            for j in range(t,stones[i]-1,-1):
                dp[j] = max(dp[j],dp[j-stones[i]]+stones[i])
        return tS-2*dp[t]

1105. 填充书架（model-IV 条件限制）

题目链接：1105. 填充书架
题目大意：给定一个数组 books ，其中 books[i] = [thicknessi, heighti] 表示第 i 本书的厚度和高度。你也会得到一个整数 shelfWidth 。
按顺序将这些书摆放到总宽度为 shelfWidth 的书架上。
先选几本书放在书架上（它们的厚度之和小于等于书架的宽度 shelfWidth ），然后再建一层书架。重复这个过程，直到把所有的书都放在书架上。
需要注意的是，在上述过程的每个步骤中，摆放书的顺序与你整理好的顺序相同。
例如，如果这里有 5 本书，那么可能的一种摆放情况是：第一和第二本书放在第一层书架上，第三本书放在第二层书架上，第四和第五本书放在最后一层书架上。
每一层所摆放的书的最大高度就是这一层书架的层高，书架整体的高度为各层高之和。
以这种方式布置书架，返回书架整体可能的最小高度。

例如：
在这里插入图片描述

输入：books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelf_width = 4
输出：6
解释：
3 层书架的高度和为 1 + 3 + 2 = 6 。
第 2 本书不必放在第一层书架上。

解题思路：按照题意一步一步往下做,这题不好想,也不好讲,看了图片也不好懂,总之,体会吧!
时间复杂度： $O(N^2)$ N为数组长度
空间复杂度： $O (N)$

class Solution:
    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:
        n = len(books)
        dp = [1000000]*(n+1)
        dp[0] = 0
        for i in range(1,n+1):
            tmp_width,j,h = 0,i,0
            while j>0:
                tmp_width += books[j-1][0]
                if tmp_width > shelfWidth:
                    break
                h = max(h,books[j-1][1])
                dp[i] = min(dp[i],dp[j-1]+h)
                j -= 1
        return dp[n]

1920. 播放列表的数量（model-IV 条件限制）

题目链接：920. 播放列表的数量
题目大意：你的音乐播放器里有 N 首不同的歌，在旅途中，你的旅伴想要听 L 首歌（不一定不同，即，允许歌曲重复）。请你为她按如下规则创建一个播放列表：

每首歌至少播放一次。
一首歌只有在其他 K 首歌播放完之后才能再次播放。
返回可以满足要求的播放列表的数量。由于答案可能非常大，请返回它模 10^9 + 7 的结果。

例如：

输入：N = 3, L = 3, K = 1
输出：6
解释：有 6 种可能的播放列表。[1, 2, 3]，[1, 3, 2]，[2, 1, 3]，[2, 3, 1]，[3, 1, 2]，[3, 2, 1].

输入：N = 2, L = 3, K = 0
输出：6
解释：有 6 种可能的播放列表。[1, 1, 2]，[1, 2, 1]，[2, 1, 1]，[2, 2, 1]，[2, 1, 2]，[1, 2, 2]

输入：N = 2, L = 3, K = 1
输出：2
解释：有 2 种可能的播放列表。[1, 2, 1]，[2, 1, 2]

解题思路：遗留问题,不多解释,太抽象了,这道题! 什么新歌老歌.动态规划,果然是头大.
时间复杂度： $O (N L)$ N和L由题意中获取.
空间复杂度： $O (L)$

class Solution:
    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
        dp = [0 for _ in range(n+1)]
        dp[0] = 1
        for i in range(1,goal+1):
            # 播放新歌
            if i <=k:
                dp[i] = dp[i-1]*(n-i+1)
                dp[i-1] = 0
            else:
                tmp = [0 for _ in range(n+1)]
                for j in range(k+1,n+1):
                    tmp[j] = (dp[j-1]*(n-j+1)+dp[j]*(j-k))% (10**9+7)
                dp = tmp
            # print(dp)
        return dp[-1]