动态规划基础（python）day1

        最近开始备战蓝桥杯比赛，在往届的比赛题当中我们可以发现动态规划占比是很高的，并且在以后的面试中也有许多面试题是和动态规划有关，所以学习并掌握动态规划是十分有必要的。

概念

我们先来梳理一下动态规划的概念。

动态规划的核心在于用空间换取时间，它的原理就是就是利用历史记录，来避免重复运算。而这些历史记录，所以我们需要用一些变量来保存，一般是用一维数组和二维数组来保存。

我们借助力扣的题库（动态规划（基础版））帮助我们学习并掌握动态规划。动态规划（基础版） – 学习计划 – 力扣（LeetCode）全球极客挚爱的技术成长平台

斐波那契类型

        第一题：爬楼梯

题目理解

我们需要走到第 n 阶楼梯，每次可以选择爬 1 或 2 个台阶。问：有多少种不同的方法可以爬到第 n 阶？

动态规划的核心思想

动态规划的核心是通过状态转移方程将问题分解为子问题，并利用子问题的解来推导出最终答案。

寻找状态转移方程

我们可以从问题的描述中找到关键点：“每次可以爬 1 或 2 个台阶”。这意味着：

因此，走到第 n 阶的方法数等于走到第 n-1 阶的方法数加上走到第 n-2 阶的方法数。这就是我们的状态转移方程：

f(n)=f(n−1)+f(n−2)f(n)=f(n−1)+f(n−2)

边界条件

状态转移方程需要初始条件才能开始计算：

代码实现

有了状态转移方程和边界条件，我们就可以用动态规划来解决问题了。以下是代码实现：

def climbStairs(self, n: int) -> int:
        if n == 0:
            return 1
        if n == 1:
            return 1
        
        # 初始化 dp 数组
        dp = [0] * (n + 1)
        
        # 初始条件
        dp[0] = 1
        dp[1] = 1
        
        # 填充 dp 数组
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        
        return dp[n]

进一步优化：滚动数组思想

虽然我们已经用动态规划解决了问题，但代码仍有优化空间。通过滚动数组思想，我们可以将空间复杂度从 O(n) 优化到 O(1)。

核心思想

在动态规划中，我们只需要保存当前计算所需的前两个状态（即 f(i−1)f(i−1) 和 f(i−2)f(i−2)），而不需要保存整个 dp 数组。通过不断更新这两个状态，我们可以在常数空间内完成计算。

优化后的代码

以下是使用滚动数组思想优化后的代码：

def climbStairs(self, n: int) -> int:
    a, b = 1, 1  # 初始化 a = dp[0], b = dp[1]
    for _ in range(n - 1):  # 循环 n-1 次
        a, b = b, a + b  # 更新 a 和 b
    return b  # 返回 dp[n]

        这样是不是更加简单易懂呢？

        第二题：斐波那契数

题目分析

这道题比上一题更简单，因为它直接给出了边界条件和动态规划转移方程。我们只需要根据题目提供的信息，直接写出代码即可。

class Solution:
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        
        # 创建一个长度为 n+1 的列表，避免索引越界
        num = [0] * (n + 1)
        num[0] = 0
        num[1] = 1
        
        # 计算斐波那契数列
        for i in range(2, n + 1):
            num[i] = num[i - 1] + num[i - 2]
        
        return num[n]

进一步优化：滚动数组思想

def fib(self, n: int) -> int:
        if n < 2:
            return n
        
        p, q, r = 0, 0, 1
        for i in range(2, n + 1):
            p, q = q, r
            r = p + q
        
        return r

        第三题： 第 N 个泰波那契数

  这道题遇上两道题一致，各位同学可以自己写完后再来查看

def tribonacci(self, n: int) -> int:
    if n == 0:
        return 0
    if n == 1 or n == 2:
        return 1
    
    # 初始化前三个泰波那契数
    a = 0  # T(0)
    b = 1  # T(1)
    c = 1  # T(2)
    
    # 计算泰波那契数列
    for i in range(3, n + 1):
        a, b, c = b, c, a + b + c  # 更新 a, b, c
    
    return c  # 返回 T(n)

        第四题： 使用最小花费爬楼梯

        这道题比前三道题改了一个地方：前两个的方法/值的和  ->  前两个之间的最小花费。

        我们需要先将创建长度为 n+1 的数组 dp，其中 dp[i] 表示达到下标 i 的最小花费。由于可以选择下标 0 或 1 作为初始阶梯，因此有 dp[0]=dp[1]=0。

        根据前几题的思路我们写出这道题的动态规划转移方程：

dp[i] = min(dp[i – 1] + cost[i – 1], dp[i – 2] + cost[i-2])

        那么代码就可以写出：

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        prev = curr = 0  # 初始化 prev 和 curr
        for i in range(2, n + 1):
            nxt = min(curr + cost[i - 1], prev + cost[i - 2])  # 计算下一步的最小花费
            prev, curr = curr, nxt  # 更新 prev 和 curr
        return curr  # 返回

        第五题：打家劫舍

        这道题是我们遇到的第一道中等难度的题，我们依旧是先看题目。这道题与上几道题不同的地方在于:（上几道题）在前两个间讨论 -> (本题)在三个之间讨论。

        这句“如果两件相邻的房屋在同一晚上被小偷闯入，系统会自动报警”我们可以理解为：

在连续的三间房子内， 中间  比较(> or <) 左边+右边 ，谁更大我们取更大的那个数为第i位。这样是不是清晰明了起来了。

        那么动态规划转移方程可以得出

dp[i] = max(dp[i-1],dp[i-2] + nums[i])

        到这一步我们就需要重新讨论边界值了，你看这个动态规划转移方程用到了三个值，但是题目给的是

1 <= nums.length <= 100

        所以前两个数我们要先算出来，即：

dp[0] = nums[0]

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

        那么代码就可以写出了：

def rob(self, nums: List[int]) -> int:
    n = len(nums)
    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-1],dp[i-2] + nums[i])
    return dp[n-1]

        这道题我们仍然可以用滚动数组来优化：

def rob(self, nums: List[int]) -> int:
    n = len(nums)
    if n == 1:
        return nums[0]
    
    # 初始化前两个状态
    first = nums[0]  # 偷窃第 0 个房屋的最大金额
    second = max(nums[0], nums[1])  # 偷窃第 0 或第 1 个房屋的最大金额
    
    # 动态规划递推
    for i in range(2, n):
        first, second = second, max(first + nums[i], second)  # 更新状态
    
    return second  # 返回最终结果

        第六题： 删除并获得点数

        这道题就是相较于上一道题难度稍大，也更加有意思的一道题，我们首先来看题：

        我们先来拆解题意，中间的那一段话可以理解为我选接我选择数字2那么数字1和3全部删去，我得到了所有数字2的和，如果是3，那我们删除2,4.最后我们要找到收益最大的数字，你是否想到了上一题的连续三个数的找最大？这道题的构想也是一样的，不过我们需要先对原始数据进行处理。

        要想得到处理后的元素我们要先找到元素的个数即nums中的最大值：

maxVal = max(nums)

        我们可以创建数组total并将数据处理再用打家劫舍得出答案。

        代码如下：

def deleteAndEarn(self, nums: List[int]) -> int:
    # 找到 nums 中的最大值
    maxVal = max(nums)
        
    # 创建一个数组 total，用于存储每个数字对应的总点数
    total = [0] * (maxVal + 1)
    for val in nums:
        total[val] += val
        
    # 定义一个 rob 函数，用于计算不偷相邻房屋的最大点数
    def rob(nums: List[int]) -> int:
        size = len(nums)
        first, second = nums[0], max(nums[0], nums[1])
        for i in range(2, size):
            first, second = second, max(first + nums[i], second)
        return second
        
    # 调用 rob 函数计算最大点数
    return rob(total)

        经过这一天的学习你是否对动态规划学习有了些许兴趣，希望第一天的斐波那契类型的动态规划对你有些许的帮助！

作者：雪野湖\’