[数据结构与算法]python动态规划入门，从斐波那契数列到01背包

? ? ? ? 在学习动态规划之前，我们先明确一下几点——什么是动态规划？动态规划有什么用？什么情况下使用动态规划？

? ? ? ? 什么是动态规划？

? ? ? ? 动态规划是运筹学的一个分支，是对一类问题的最优解法，在实际问题中表现为以空间换取时间。不同于贪心算法，动态规划的每一个状态绝对是由上一个状态推导而出。

????????动态规划有什么用？

? ? ? ??动态问题将已解决的子问题保存下来，需要子问题答案时可以直接获得，一些问题不使用动态规划时间复杂度可以达到（2**n）而使用动态规划可以有效降低其时间复杂度。

????????什么情况下使用动态规划？

? ? ? ? 以下几类问题适合使用动态规划解决：

1.计数

????????有多少种方式走到右下角

????????有多少种方法选出k个数使得和是Sum

2.求最大最小值

????????从左上角走到右下角路径的最大数字和

????????最长上升子序列长度

3.求存在性

? ? ? ? 取石子游戏，先手是否必胜

????????能不能选出k个数使得和是Sum

反之，若题目要求你把所有情况列举出来，如“无价值属性01背包问题，要求你输出所有重量为w的情况”

? ? ? ? 在正式讲解例题前务必熟记动态规划问题解决思路

????????动态规划问题的解决思路：

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

有些同学python基础没打好，只知道有python，却不知道如何在python中创建数组，这里提供浅拷贝和深拷贝两种方法，平时使用浅拷贝足以：

# 复制n遍的浅拷贝“创建数组”
# 创建一维数组
list_1 = [0]*5
print(list_1)
print(list_1[1])

# 创建二维数组
list_2 = [[0]*5]*4
print(list_2)
print(list_2[3][4])  # 4行5列数组

# 创建三维数组
list_3 = [[[0]*5]*4]*3
print(list_3)
print(list_3[2][3][4]) 

# 真正意义上创建数组
list_1 = [0 for _ in range(5)]
print(list_1)
print(list_1[1])

list_2 = [[0 for _ in range(5)] for _ in range(4)]
print(list_2)
print(list_2[3][4])  # 4行5列数组

list_3 = [[[0 for _ in range(5)] for _ in range(4)] for _ in range(3)]
print(list_3)
print(list_3[2][3][4])

1.斐波那契数列

代码如下：

def List_Fibonacci(n):
    if n==1:
        return 0
    elif n==2:
        return 1
    a = 0
    b = 1
    i = 3
    while i <= n:
        a,b = b,a+b
        i += 1
        print(b,end=" ")
    return b


# 递推是一种最简单的状态转移

a = List_Fibonacci(31)

这里我们学习了最简单的状态转移——递推，每次的状态皆有前两次状态得到

2.爬楼梯

给定一个n(1<=n<=5)代表总共有  阶楼梯，一开始在第0阶，每次可以爬1或者2个
台阶，问总共有多少种不同的方法可以爬到楼顶。

代码如下：

def climbStairs(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    a = 1
    b = 2
    i = 3
    while i <= n:
        a,b = b,a+b
        i += 1
    return b

这题其实和斐波那契数列异曲同工，第i层只能由第i-1和i-2层得到，所以我们获得状态转移方程

dp[i] = dp[i-1] + dp[i-2]

得解

3.爬楼梯最小花费

给定一个n(n<=1000)，再给定一个n个整数的数组cost， 其中cost[i]是从楼梯第i个
台阶向上爬需要支付的费用。一旦支付此费用，即可选择向上爬一个或者两个台阶。
可以选择从下标为0或下标为1的台阶开始爬楼梯，请计算并返回达到楼梯顶部的最低花费。

代码如下：

def climbStairs(n,cost):
    f = [0]*1001
    i = 2
    while i <= n:
        f[i] = min(f[i-1]+cost[i-1],f[i-2]+cost[i-2])
        i += 1
    return f

要求最小花费，那就是求从哪种状态来的花费最小，得到状态转移方程

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

得解

4.删除并获得点数

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

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

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

代码如下：

def deleteAndEarn(self,nums):
    numdict = dict()  # 创建一个字典（map）
    numlist = []    #
    for num in nums:
        if num in numdict.keys():  # 倘若已经出现过的数字则储存进去
            numdict[num] += num
        else:   # 未出现过的数字则添加进去
            numdict[num] = num
            numlist.append(num)     # 储存所有的数字类型
    # 然后用动态规划，其实就是打家劫舍问题
    n = len(numlist)
    sortnuml = sorted(numlist)      # sort 是应用在 list 上的方法，sorted 可以对所有可迭代的对象进行排序操作

    dp = [0] * (n + 1)
    dp[1] = numdict[sortnuml[0]]

    for i in range(1, n):
        # 如果上一个不是连续的
        if sortnuml[i] != sortnuml[i - 1] + 1:
            dp[i + 1] = dp[i] + numdict[sortnuml[i]]
        else:
            dp[i + 1] = max(dp[i], dp[i - 1] + numdict[sortnuml[i]])

    return dp[n]

有些同学可能开始懵逼了，别急，先看下一题获得思路：

5.打家劫舍

给定一个整数n(1<=n<=100)，再给定一个n个整数的数组nums，每个整数可以选择取或者不取，如果第i个整数取，那么 第i-1或者i+1个整数就不能取。

要求按照上述规则选取一些整数，使得选出来的整数得到的总和最大，返回这个最大值。

代码如下：

def rob(n,nums):
    f = [0]*101
    f[0] = nums[0]  # 设置初始值
    i = 1
    while i < n:
        if i == 1:
            f[i] = max(nums[0],nums[1])  # 防止数组下标越界
        else:
            f[i] = max(f[i-1],f[i-2]+nums[i])
        i += 1
    return f[n-1]

这个题目要求我们相邻的数不能选，并求出最大的总和，我们假设dp[i]就是前i个数最大总和，则dp[i]只能由dp[i-1] 和之前的dp[i-2]得到，如果是前者则不能添加第i个数，如果是后者则可以将第i个数加入，得到状态转移方程：

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

得解。

看到这里，第四题已经很明了了，题目要求删除nums[i]+1或nums[i]-1的值，那我们直接将原有数组排序，按照打家劫舍问题求解即可

6.最大子数组和

给定一个整数n(1<=n<=10**5)，再给定一个n个整数的数组nums，请找出一个具有 最大和的连续子数组，返回其最大和。

代码如下：

def andearn(nums,n):
    f = [0]*(n+1)
    i = 1
    # maxvalue = 0
    while i <= n:
        f[i] = max(nums[i-1],(f[i-1]+nums[i-1]))
        # maxvalue = max(maxvalue,f[i])
        i += 1

    return max(f)

我们假设dp[i]为前i个数字所组成数组中的最大连续数组，可得状态转移方程：

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

得解

7.整数拆分

给定?个正整数 n，将其拆分为?少两个正整数的和，并使这些整数的乘积最?化。返回
你可以获得的最?乘积。

代码如下：

def integerBreak(n):
    f = [0]*(n+1)
    f[0] = 0
    f[1] = 1
    f[2] = 1
    for i in range(3,n+1):
        for j in range(1,i):
            f[i] = max(f[i],max((i-j)*j,f[i-j]*j))  # 讨论拆分情况
    return f[n]

本题也有其规律，多次测试会发现最优解为，n个3和0或一个4相乘，比如10等于3*3*4 9等于3*3*3 8等于3*3*2，根据规律运用贪心可将时间复杂度进一步降低

8.不同路径

????????相信同学们对创建一维数组解决问题已经了如指掌，可是实际问题可能要考虑更多的变量：

?个机器?位于?个 m x n ?格的左上?（起始点在下图中标记为 “Start” ）。
机器?每次只能向下或者向右移动?步。机器?试图达到?格的右下?（在下图中标记为
“Finish” ）。
问总共有多少条不同的路径？

代码如下：

def dfs(m,n):
    f = [[0]*n]*m
    for i in range(m):
        f[i][0] = 1
    for j in range(n):
        f[0][j] = 1
    for a in range(1,m):
        for b in range(1,n):
            f[a][b] = f[a-1][b] + f[a][b-1]
    return f[m-1][n-1]

有草稿纸的同学请画出表格，机器人从（0，0）到（m-1，n-1）,我们假设移动到一格的路径有dp[i][j]种，由于机器人只能向右或向下移动，那么dp[i][j]只能由dp[i-1][j]和dp[i][j-1]得到，状态转移方程：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

得解

9.01背包问题

有N件物品和?个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是
value[i] 。每件物品只能??次，求解将哪些物品装?背包?物品价值总和最?。
物品0 重量1 价值15，物品1 重量3 价值20，物品2 重量4 价值30
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])   # 从下标为[0-i]的物品?任意取，放进容量为j的背包，价值总和
最?是多少

# 01背包问题对于第i个物品考虑选与不选

def bag(n,w,weight,value):
     f = [[0]*(w+1)]*n   # n是物品序号，w是背包重量
     for j in range(1,w+1):
         f[0][j] = 15
     for i in range(1,n):
        for j in range(0,w+1):
                if j < weight[i]:
                    f[i][j] = f[i-1][j]
                else:   # 选不选
                    f[i][j] = max(f[i-1][j],f[i-1][j-weight[i]]+value[i])

     return f[n-1][w]

有草稿纸同学一定要画表格，n*w的表格，n代表物品，w代表背包重量，那么对于第i件物品dp[i][j]选不选就是问题的核心，得到状态转移方程：

dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])

得解

10.完全背包问题

代码如下：

def bag(n, w, weight, value):
    f = [[0] * (w + 1)] * n  # n是物品序号，w是背包重量
    for i in range(0, n):
        for j in range(0, w + 1):
            if j < weight[i]:
                f[i][j] = f[i - 1][j]
            else:  # 选不选
                f[i][j] = max(f[i - 1][j], f[i - 1][j - weight[i]] + value[i])

    return f[n - 1][w]

完全背包问题与01背包问题的区别在于一件物品是否可以多次选取，如果你已经理解完全背包问题和01背包问题，试着结合两者解决多重背包问题

11.滚动数组

? ? ? ? 我们发现使用多维数组十分地占用空间，有没有一种办法将其降维呢？那就是使用滚动数组：

代码如下：

def bag(n, w, weight, value):
    f = [0]*(w+1)
    for i in range(0,n):
        for j in range(weight[i],w+1):
            f[j] = max(f[j],f[j-weight[i]]+value[i])
    return f[w]

关于背包问题，上文我们定义i为物品，j为背包重量，但我们可不可以当用j来表示呢?dp[j]表示背包承重为j时装入的最大价值，得到状态转移方程：

dp[j] = max(dp[j],dp[j-weight[i]+value[i])

得解。

看到这里，你对动态规划已经基本入门，获取知识的最好方法是解决问题，赶紧趁热刷题吧，想必你会有新收获！