算法第三十二天--动态规划part01（第九章）

一.动态规划理论基础

1.#什么是动态规划

    Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

2..动态规划分类

1.基础题目

2.背包问题

3.打家劫舍

4.股票问题

5. 子序列问题

 3.动态规划的解题步骤：

对于动态规划问题，拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

实战训练

1.斐波那契数

 509. 斐波那契数 - 力扣（LeetCode）

思路：

1.     确定DP数组以及其下标含义：dp[i]的定义为：第i个数的斐波那契数值是dp[i]
2. 递推公式：dp[i] = dp[i-1] +dp[i-2]
3. dp数组如何初始化:dp[0] = 0, dp[1] = 1
4. 遍历顺序：从前往后
5. 打印dp数组

class Solution:
    def fib(self, n: int) -> int:
    
        if n == 0:
            return 0
        #初始化 
        dp = [0]*(n+1)
        dp[0] = 0
        dp[1] = 1
        # 遍历顺序: 由前向后。因为后面要用到前面的状态
        for i in range(2, n+1):
            #递推公式
            dp[i] = dp[i-1] + dp[i-2]
        #  返回答案 
        return dp[n]
        

2.爬楼梯

70. 爬楼梯 - 力扣（LeetCode）

思路：

本题大家如果没有接触过的话，会感觉比较难，多举几个例子，就可以发现其规律。

爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。

那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。

所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想到动态规划了。

唯一的区别是，没有讨论dp[0]应该是什么，因为dp[0]在本题没有意义！

class Solution:
    def climbStairs(self, n: int) -> int:
        #当前这个阶有多少种方法依赖于前两种
        #dp[i]:达到i阶有dp[i]种方法
        if n == 0:
            return 0
        dp = [0]*(n+1)
        dp[0] = 1
        dp[1] = 1
        
        for i in range(2, n+1):
            dp[i] = dp[i-1] +dp[i-2]
        return dp[n]

3.使用最小花费爬楼梯

746. 使用最小花费爬楼梯 - 力扣（LeetCode）

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        #dp[i] 表示下表为i时的最低消费
        n = len(cost)
        dp = [0]*(n+1)
        if len(cost) == 0:
            return 0
        
        dp[0] = 0
        dp[1] = 0

        for i in range(2, n+1):
            dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
        return dp[n]

今天结束啦！动态规划开始题目比较简单没有很难！