7 动态规划

下面的例子不错： 对于动态规划，能学到不少东西；

你要清楚每一步都在做什么，划分细致就能够拆解清楚！

 xk. - 力扣（LeetCode）

labuladong的算法笔记-动态规划-CSDN博客

动态规划是一种强大的算法设计策略，用于解决具有重叠子问题和最优子结构特点的问题。在面对动态规划类题目时，遵循以下步骤可以帮助你系统地解决问题：

1. 定义状态

• 确定变量：识别哪些变量会影响问题的解。例如，在背包问题中，关键变量可能是物品的重量和价值，以及剩余的背包容量。
• 状态表示：用这些变量定义状态。例如，dp[i][w] 可能表示前i个物品放入容量为w的背包所能获得的最大价值。

2. 状态转移方程

• 建立关系：找到状态之间的关系，即如何从一个状态转移到另一个状态。这通常涉及到一个递推公式。例如，在斐波那契数列中，F(n) = F(n-1) + F(n-2)。
• 边界条件：确定递推公式的起始状态，通常是最简单的情况，例如 dp[0][w] = 0（背包问题中没有物品时的价值）。

3. 选择方向

• 自底向上：从最简单的状态开始，逐步构建更复杂的状态。这种方法通常使用循环实现，避免了重复计算。
• 自顶向下：从复杂的状态开始，递归地解决子问题。这种方法通常使用递归和记忆化（memoization）来避免重复计算。

4. 初始化

• 初始状态：根据问题的性质初始化DP数组。例如，所有状态初始化为0或无穷大。

5. 计算

• 填充DP表：根据状态转移方程填充DP表或数组。确保按正确的顺序填充，以便在计算每个状态时，所需的前驱状态已经被计算。

6. 返回结果

• 解析答案：DP过程完成后，根据问题要求解析出最终答案。这可能是DP表中的某个特定值，也可能是回溯整个DP过程找到最优解的具体方案。

7. 复杂度分析

• 时间复杂度：通常由状态的数量和状态转移的复杂度决定。
• 空间复杂度：由存储状态所需的空间决定，可以通过滚动数组等方式优化空间复杂度。

1 70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

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

这是一个简单的动态规划的问题：

分解问题：不积硅步无以至千里！

假设：当前到了第x层,并且小于x层的走法f(x)我们都知道。

那么后面如何求呢？

1. 第一个阶梯、第二个阶梯都是1下就能走到！
2. y = x+1,那么 f（y） = f(y-1) + f(y-2), 想要上到第y步， 一定是从前面阶梯走过来的。

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [1] * (n+1)
        
        for i in range(2,n+1):
            dp[i] = dp[i-1] + dp[i-2]
        #print(dp)
        return dp[n]

2 198. 打家劫舍 

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

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

相邻不能同时偷！

示例 1：

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

在做这一个题目的时候：

f(x): 到第x个房间能得到的最大收益；

我也是设定：加入到了第X个房间，那么之前的状态（到房间能得到的最大收益）我都是知道的。所以，f(X+1) 怎么做才能最大呢？

怎么能偷到x+1个房子，由x-1过来的，x-2过来的（开始我没考虑到这点）。

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

3 322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

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

1. 递归；
2. 动态规划；

有硬币：【q,w,e】

思想： 

比如7个硬币怎么使用最少的硬币进行组合呢？

f(7) = min(f(7-q),f(7-w),f(7-e)) + 1

还有个特殊条件： f(7-q),f(7-w),f(7-e) 存在组合（基石，不然无法站住脚）；

我这个思路不是特征的好。

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
 
        if amount==0:
            return 0 
            
        coins = sorted(coins)
 
        dp = [0] * (amount+1)
 
        for i in range(amount+1):
            for coin in coins:
                if i-coin==0:
                    dp[i] = 1
                elif i-coin>0:
                    if dp[i]==0:
                        # 
                        if dp[i-coin]==0:
                            dp[i]==0
                        else:
                            dp[i] = dp[i-coin] + 1 #min(, dp[i])
                    else:
                        if dp[i-coin]==0:
                            dp[i]==0
                        else:
                            dp[i] = min(dp[i-coin] + 1, dp[i])
                else:
                    break
        print(dp)
        return -1 if dp[amount]==0 else dp[amount]
 
        
        
        # def sub_x(amount):
        #     if amount==0:
        #         return 0
 
        #     if amount < 0 or amount<coins[0]:
        #         return -1
 
        #     temp = -1
        #     for coin in coins:
        #         x = sub_x(amount - coin) # -1, >=0
        #         if x == -1:
        #             continue
        #         if temp==-1:
        #             temp = x+1
        #         else:
        #             temp = min(x+1, temp)
        #     return temp
 
        return sub_x(amount)
 
 

思路二 ：陈奕迅的背包

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        
        n = len(coins)
        dp = [[amount+1] * (amount+1) for _ in range(n+1)]    # 初始化为一个较大的值，如 +inf 或 amount+1
        # 合法的初始化
        dp[0][0] = 0    # 其他 dp[0][j]均不合法
        
        # 完全背包：套用0-1背包【遍历硬币数目k】
        for i in range(1, n+1):                     # 第一层循环：遍历硬币
            for j in range(amount+1):               # 第二层循环：遍历背包
                for k in range(j//coins[i-1]+1):    # 第三层循环：当前硬币coin取k个 (k*coin<=amount)
                    dp[i][j] = min( dp[i][j], dp[i-1][j-k*coins[i-1]] + k )
 
        ans = dp[n][amount] 
        return ans if ans != amount+1 else -1

 思想：

1. dp[i][j]: 使用i个硬币拼成J元最小个数;
2. 如何判断是否放入第i+1 个硬币呢？ 当前的容量不足以满足硬币金额，那么最好的揭发就是dp[i-1][j], 最好的解决策略在之前。 当前的容量>金额: 有操作的空间， min（放入+1，不放入）

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # 11 [1,2,5]
        coin_len = len(coins)
        dp = [[amount+1]*(amount+1) for _ in range(coin_len+1)]
        #coins = sorted(coins)
        # 多大空间
        dp[0][0] = 0
 
        for i in range(1,coin_len+1):
            for j in range(amount+1):
                coin = coins[i-1]
                if j < coin:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-coin]+1)
        # for j in range(1, coin_len+1):
        #     coin = coins[j-1]
        #     for i in range(amount+1):
        #         # 当前能够到达的最大距离
        #         for x in range(i//coin+1):
        #             dp[j][i] = min(dp[j][i], dp[j-1][i-coin*x]+x)
        #print(dp)
        return -1 if dp[coin_len][amount]==(amount+1) else dp[coin_len][amount]