文章目录 1.简介2.背包问题3.最长非降子序列
1.简介
什么是动态规划
动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度，因此它比回溯法、暴力解法要快的多。
问题描述
假设我们有n件物品，分别编号为1, 2…n。其中编号为i的物品价值为vi，它的重量为wi。为了简化问题，假定价值和重量都是整数值。
现在，假设我们有一个背包，它能够承载的重量是W。现在，我们希望往包里装这些物品，使得包里装的物品价值最大化，
那么我们该如何来选择装的东西呢？
解题思路
首先，构造状态转移方程
1.我们先创建一个二维数组dp[][],行：物品种类，列：重量
2.dp[i][j] 含义为 物品种类为i种,最大重量为j
方程可得
3.当重量足够装这个物品时，即 j >= w[i]时 dp[i][j] = max(dp[i-1][j - w[i]] + v[i],dp[i-1][j])
4.当不够时，dp[i][j] = dp[i-1][j]
python代码
w = [1, 4, 3, 1] #重量v = [1500, 3000, 3000, 3000] #价值n = 4 #总重量res = [[0 for col in range(n + 1)] for raw in range(len(v))]def pack(v, w, n): for i in range(len(v)): #各种物品 for j in range(n + 1): #重量 if j >= w[i]: res[i][j] = max(res[i - 1][j], res[i - 1][j - w[i]] + v[i]) else: res[i][j] = res[i - 1][j] return res[len(v) - 1][n]print(pack(v, w, n)) 3.最长非降子序列问题描述
一个序列有 N 个数：A[1],A[2],…,A[N]，求出最长非降子序列的长度
解题思路
构造状态转移方程
1.创建一个一维数组dp，dp[i]用来存储当前第i个数据的非降子序列长度
2.定义一个curlen来表示最长的非降子序列长度
可得方程
3.如果args[i] >= args[j]，然后比较dp[i] <= dp[j]，那么dp[i] = dp[j] + 1
4.这样比较完j = range(0,i)，就可以得到dp[i]
5.再用curlen存储最长的非降子序列长度
python代码：
def lis(*args): curnum = 1 res = [0] * len(args) print(len(args)) for i in range(len(args)): res[i] = 1 for j in range(i): if args[j] <= args[i] and res[i] < res[j] + 1: res[i] = res[j] + 1 if res[i] > curnum: curnum = res[i] print(res) return curnumprint(lis(5, 7, 3, 4, 6, 8))