1、斐波那契数列
# -*- coding:utf-8 -*-
def fib(n):
"""
递归方式实现斐波那契数列---时间复杂度O(2^n),空间复杂度O(n)
:param n:
:return:
"""
if n < 2:
return n
else:
return fib(n-1) + fib(n-2)
def fib1(n):
"""
dp方式实现斐波那契数列---时间复杂度O(n),空间复杂度O(1)
:param n:
:return:
"""
if n < 2:
return n
dp = [0, 1] # 初始化
for i in range(2, n + 1):
# dp.append(dp[i-1] + dp[i - 2]) # 空间复杂度高 O(n)
dp[0], dp[1] = dp[1], dp[0] + dp[1] # 空间复杂度 O(1)----滚动dp一维数组
return dp[-1]
if __name__ == '__main__':
print(fib(8))
print(fib1(8))
变长的dp动画
滚动的dp动画
2、爬楼梯
题目：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的⽅法可以爬到楼顶呢？
思路：
递推公式：dp[i] = dp[i-1] +dp[i-2]
dp[i]存储的是上第i阶台阶的方法总数：要不就是i-1阶爬一阶上来，要不就是i-2阶爬2个台阶上来
初始化：和斐波那契数列一波相比只是初始不一样，第一个台阶的方法1种，第二个台阶方法是2种
遍历顺序：遍历台阶，从第一阶向后
def fib1(n):
"""
dp方式实现爬楼梯---时间复杂度O(n),空间复杂度O(1)
:param n:
:return:
"""
if n < 2:
return n
dp = [1, 2] # 初始化这里和斐波那契不一样
for i in range(2, n + 1):
# dp.append(dp[i-1] + dp[i - 2]) # 空间复杂度高 O(n)
dp[0], dp[1] = dp[1], dp[0] + dp[1] # 空间复杂度 O(1)----滚动dp一维数组
return dp[1]
return dp[-1]
题目：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的⽅法可以爬到楼顶呢？
思路：
递推公式：dp[i] = dp[i-1] +dp[i-2]
dp[i]存储的是上第i阶台阶的方法总数：要不就是i-1阶爬一阶上来，要不就是i-2阶爬2个台阶上来
初始化：和斐波那契数列一波相比只是初始不一样，第一个台阶的方法1种，第二个台阶方法是2种
遍历顺序：遍历台阶，从第一阶向后
3、使⽤最⼩花费爬楼梯
LeetCode地址：力扣
题目：数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。
请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
思路：
递推公式：dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]
到达第i个台阶所花费的最少体⼒为dp[i]
初始化：dp[0],dp[1] = cost[0]，cost[1]
这里dp[1]并没有取min（cost[0],cost[1]）因为这里如果去了cost[0],那就没有从
cost[1]作为起点的情况就给排除了，最后的结果也是取最后两个值的最小值也体现
了这个点
到达第i个台阶所花费的最少体⼒为dp[i]
遍历顺序：遍历台阶，即是遍历cost
def fun1(cost):
dp = cost[0:2]
for i in range(2, len(cost)):
dp[0], dp[1] = dp[1], min(dp[0], dp[1]) + cost[i]
return min(dp)
LeetCode地址：力扣
题目：数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。
请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
思路：
递推公式：dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]
到达第i个台阶所花费的最少体⼒为dp[i]
初始化：dp[0],dp[1] = cost[0]，cost[1]
这里dp[1]并没有取min（cost[0],cost[1]）因为这里如果去了cost[0],那就没有从
cost[1]作为起点的情况就给排除了，最后的结果也是取最后两个值的最小值也体现
了这个点
到达第i个台阶所花费的最少体⼒为dp[i]
遍历顺序：遍历台阶，即是遍历cost
4、不同路径
LeetCode地址：https://leetcode-cn.com/problems/unique-paths/
题目：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
思路：
递推公式：[i][j]=dp[i - 1][j] + dp[i][j - 1]
走到[i][j]的网格的路径总数，是来自从上、从左来的路径总数
初始化：dp[m][n] = 都是1
遍历顺序：第一行和第一列只有一种路径，所以遍历行从1，列也从1
def uniquePathsWithObstacles(obstacleGrid):
"""二维dp数组解决不同路径问题"""
m, n = len(obstacleGrid), len(obstacleGrid[0])
dp = [[1 for x in range(n)] for y in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[-1][-1]
def uniquePathsWithObstacles(obstacleGrid):
"""一维dp数组解决不同路径问题"""
# 不同路径1中可以使用一维dp数组def uniquePaths(m, n):
dp = [1 for x in range(n)]
for i in range(1, m):
for j in range(1, n):
dp[j] += [j - 1]
return dp[-1]
5、不同路径 II
LeetCode地址：https://leetcode-cn.com/problems/unique-paths/
题目：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
思路：
递推公式：[i][j]=dp[i - 1][j] + dp[i][j - 1]
走到[i][j]的网格的路径总数，是来自从上、从左来的路径总数
初始化：dp[m][n] = 都是1
遍历顺序：第一行和第一列只有一种路径，所以遍历行从1，列也从1
题⽬链接：https://leetcode-cn.com/problems/unique-paths-ii/
与不同路径的区别
（1）遇到障碍物，说明到达这个网格的路径总数为0
（2）遍历顺序：第一行如果有障碍物，从障碍物向后就不能走了
第一列如果有障碍物，从障碍物向下就不能走了
def uniquePathsWithObstacles(obstacleGrid):
"""二维dp数组解决不同路径问题"""
m, n = len(obstacleGrid), len(obstacleGrid[0])
dp = [[1 for x in range(n)] for y in range(m)]
for i in range(0, m):
for j in range(0, n):
if obstacleGrid[i][j] == 1:#遇到障碍物走到这个网格的路径就为0
dp[i][j] = 0
elif i == 0 and j == 0:
pass
elif i == 0 and j > 0:
dp[i][j] = dp[i][j - 1]
elif j == 0 and i > 0:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[-1][-1]
def uniquePathsWithObstacles(obstacleGrid):
"""一维dp数组解决不同路径问题"""
m, n = len(obstacleGrid), len(obstacleGrid[0])
dp = [1 for x in range(n)]
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 1:
dp[j] //= 2 #遇到障碍物只是阻挡了一个方向所以除以2
else:
dp[j] += dp[j - 1]
return dp[-1]
6、整数拆分
LeetCode地址343题： 力扣
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
思路：
递推公式：dp[i] = max(dp[i], dp[i-j]*j, (i-j)*j)
列举拆分所有的情况，dp[i]依赖dp[i-j]的写法
比如：dp[3]拆分情况----
首先尝试拆出来1----dp[3]=0、1*2=2、1*dp[2]=1----dp[3]=2
再次尝试拆出来2----dp[3]=2、2*1=2、2*dp[1]=0----dp[3]=2
dp[4]拆分情况----
首先尝试拆出来1------dp[4]=0、1*3=3、1*dp[3]=2-----dp[4]=3
再次尝试拆出来2------dp[4]=3、2*2=4、2*dp[2]=2-----dp[4]=4
再次尝试拆出来3------dp[4]=4、3*1=3、3*dp[1]=0-----dp[4]=4
初始化：dp[2] = 1
dp[0],dp[1]没有意义，0、1不能拆分，题目也说了从2开始
遍历顺序：遍历dp从3开始，应为2已经初始化了
拆分的场景就是从1到i的所有情况
#方法1：dp动态规划
def integerBreak(n):
dp = [0] * (n + 1)
dp[2] = 1
for i in range(3, n + 1):
for j in range(1, i):
dp[i] = max(dp[i],dp[i-j]*j, (i-j)*j)
return dp[-1]
#方法2：贪心--3这个特殊的数么有啥理论依据
def integerBreak(n):
#贪心
if n == 2:
return 1
if n == 3:
return 2
if n == 4:
return 4
result = 1
while n > 4:
result *= 3
n -= 3
result *= n
return result
背包问题+背包回溯
LeetCode地址343题： 力扣
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
思路：
递推公式：dp[i] = max(dp[i], dp[i-j]*j, (i-j)*j)
列举拆分所有的情况，dp[i]依赖dp[i-j]的写法
比如：dp[3]拆分情况----
首先尝试拆出来1----dp[3]=0、1*2=2、1*dp[2]=1----dp[3]=2
再次尝试拆出来2----dp[3]=2、2*1=2、2*dp[1]=0----dp[3]=2
dp[4]拆分情况----
首先尝试拆出来1------dp[4]=0、1*3=3、1*dp[3]=2-----dp[4]=3
再次尝试拆出来2------dp[4]=3、2*2=4、2*dp[2]=2-----dp[4]=4
再次尝试拆出来3------dp[4]=4、3*1=3、3*dp[1]=0-----dp[4]=4
初始化：dp[2] = 1
dp[0],dp[1]没有意义，0、1不能拆分，题目也说了从2开始
遍历顺序：遍历dp从3开始，应为2已经初始化了
拆分的场景就是从1到i的所有情况
6、01背包
学习视频：【动态规划】背包问题_哔哩哔哩_bilibili
学习文章：【动态规划】一次搞定三种背包问题 - 弗兰克的猫 - 博客园
题目：一个背包可以装M重的东西，物品5个，重量为[2, 2, 6, 5, 4]，价值为[3, 6, 5, 4, 6]， 问：如何装可以得到最大的价值？
def bag(bag_w, num, weights, values):
"""
01背包问题
:param bag_w: 背包容量
:param num: 物品个数
:param weights: 物品重量list
:param values: 物品价值list
:return: 描绘的二维数组
"""
# 初始化一个二维数据，放入各种情况下最佳价值，右下角就是最优解
dp = [[0 for row in range(bag_w + 1)] for column in range(num + 1)]
for row in range(1, num + 1):
for col in range(1, bag_w + 1):
if weights[row - 1] > col: # 此时背包容量col小于row物品的容量，放不下row物品
dp[row][col] = dp[row - 1][col]
else:
# 找到去掉row物品容量col - weights[row - 1]对应的row-1个物品的最大价值
t1 = dp[row - 1][col - weights[row - 1]] + values[row - 1]
t2 = dp[row - 1][col]
dp[row][col] = max(t1, t2)
# 找到装入了那些物品----背包回溯
# 从右下角开始找，判断第五个物品是否装进口袋看：装第五个物品的最优解是否大于装第四个物品的最优解，大说明装入了，不大就是没有装入
good_value = dp[-1][-1]
good_n = []
while num > 0 and bag_w > 0:
if dp[num][bag_w] > dp[num - 1][bag_w]:
good_n.append(num)
bag_w -= weights[num - 1]
num -= 1
print("背包最大价值：%s" % good_value)
print("背包物品编号：%s" % good_n[::-1])
def bag1(bag_w, num, weights, values):
# 01背包不做回溯的话，可以使用一维dp滚动数组
# 初始化一个一维数据，放入不同背包容量时最大价值
# 难点在循环顺序
dp = [0 for row in range(bag_w + 1)]
for row in range(0, num):
for col in range(bag_w, weights[row]-1, -1):
dp[col] = max(dp[col], dp[col - weights[row]] + values[row])
return dp[-1]
if __name__ == '__main__':
num = 5 # 5个物品
bag_w = 10 # 背包总容量
weights = [2, 2, 6, 5, 4] # 物品重量集合
values = [6, 3, 5, 4, 6] # 物品价值集合
bag(bag_w, num, weights, values)
bag1(bag_w, num, weights, values)
二维图解
一维图解
（1）分割等和⼦集
LeetCode地址： 力扣
题目：给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
思路：将这些nums的元素当做物品，重量=价值=nums对应元素的值，背包假设为nums的和sum(nums)的一半
转化为：背包容量sum(nums)/2，是否有恰好装满的情况（装满了，剩下的一半也是剩下物品的重量了）
递推公式： dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]) （一维）
dp[i][j] = max(dp[i-1][j], dp[i-1][j - nums[i]] + nums[i]) （二维）
初始化：初始值都为0
遍历顺序：和上面的01背包一致
def canPartition(self, nums: List[int]) -> bool:
"01背包的一维数组解法"
total = sum(nums)
if total <= 1 or total % 2 != 0:
return False
target = total // 2
dp = [0] * (target + 1)
for i in range(len(nums)):
for j in range(target, nums[i] - 1, -1):
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
return dp[-1] == target
def canPartition1(self, nums: List[int]) -> bool:
"01背包的二维数组解法"
total = sum(nums)
if total <= 1 or total % 2 != 0:
return False
target = total // 2
dp = [[0] * (target + 1)] * (len(nums)+1)
for i in range(len(nums)+1):
for j in range(nums[i], target+1):
dp[i][j] = max(dp[i-1][j], dp[i-1][j - nums[i]] + nums[i])
return dp[-1][-1] == target
（2）最后⼀块⽯头的重量 II
LeetCode地址： 力扣
题目：
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
思路：可以转化为分割等和⼦集的问题，target=total//2
不同点：（1）total不能等分的特殊情况不用处理
（2）子集问题中dp[-1]==target，
这里(total -dp[-1]) -dp[-1],含义将total分2份，一份是dp[-1]，一份是total-dp[-1]，他们差就是击碎后的最小值了，不理解我们在分析下，(total -dp[-1]) -dp[-1] === 2(target -dp[-1])，这个式子是不是target和dp[-1]的值越相近那结果是不是越小？dp[-1]如果等于target就是等分子集了，是不是就是完美粉碎了？如果还不理解dp[-1]的意义，那就在讲，转化01背包问题：target是一个背包，装石头或者上面等分子集的nums的元素，石头重量即是价值，这样取如何装找到最大价值
递推公式： dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]) （一维）
dp[i][j] = max(dp[i-1][j], dp[i-1][j - nums[i-1]] + nums[i-1]) （二维）
初始化：初始值都为0
遍历顺序：和上面的01背包一致
def lastStoneWeightII(self, stones: List[int]) -> int:
"""一维数组dp解法"""
total = sum(stones)
target = total // 2
dp = [0] * (target + 1)
for i in range(len(stones)):
for j in range(target, stones[i] - 1, -1):
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])
return total- dp[-1] - dp[-1]
def lastStoneWeightII(self, stones: List[int]) -> int:
"""二维数组dp解法"""
total = sum(stones)
target = total // 2
dp = [[0 for x in range(target + 1)] for y in range(len(stones)+1)]
for i in range(1, len(stones)+1):
for j in range(1, target+1):
if j < stones[i-1]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j - stones[i-1]] + stones[i-1])
return total- dp[-1][-1] - dp[-1][-1]
（3）目标和
LeetCode地址： 力扣
题目：
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
思路：每个元素有正负的两种情况，是否也是和分割等和⼦集、最后⼀块⽯头的重量 II问题类似，都是将nums分成两份，一份装，一份不装入，装入的是正号，不装入的是负号，是不是也像粉碎石头了？
不同点：这个背包的容量是多少呢？分隔等和子集的背包容量是total的一半，这里呢？一份正数和、一份负数和
正数和 + 负数和 = total
正数和 - 负数和 = target
正数和 = （total + target）/ 2
所以就转化为了正数和的表达式 的数目
递推公式： dp[j] = dp[j]+dp[j - nums[i]] （一维）
dp[i][j] = dp[i-1][j]+dp[i-1][j - nums[i-1]] （二维）
初始化：dp[0] =1、dp[i][0]=0 这个是二维的情况
遍历顺序：和上面的01背包一致
def findTargetSumWays(self, nums: List[int], target: int) -> int:
# 二维数组dp解法
total = sum(nums)
if target > total or (target + total) % 2 != 0 or target < -total:
# 特殊情况处理：target不能大于total,小于-total,如果功能不能整除2，就得不到正数和的部分
return 0
bag_size = (target + total) // 2
dp = [[0 for x in range(bag_size + 1)] for y in range(len(nums) + 1)]
#初始化
for z in range(len(nums)+1):
dp[z][0] = 1
for i in range(1, len(nums)+1):
for j in range(0, bag_size+1): # 这个变量背包从0开始，这里的0有具体的含义了，之前价值0是无意义的了
if j < nums[i-1]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i-1][j - nums[i-1]] + dp[i-1][j]
return dp[-1][-1]
def findTargetSumWays(self, nums: List[int], target: int) -> int:
# 一维数组dp解法
total = sum(nums)
if target > total or (target + total) % 2 != 0 or target < -total:
# 特殊情况处理：target不能大于total,小于-total,如果功能不能整除2，就得不到正数和的部分
return 0
bag_size = (target + total) // 2
dp = [0] * (bag_size + 1)
dp[0] = 1
for i in range(len(nums)):
for j in range(bag_size, nums[i] - 1, -1):
dp[j] = dp[j] + dp[j - nums[i]]
return dp[-1]
（4）一和零
题目链接：474. 一和零
题目：
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
思路：
dp[i][j]的含义：i个0和j个1组成的最大子集长度
递推公式： dp[i][j] = max(dp[i][j], dp[i - m_sum][j - n_sum] + 1)
初始化：0，组成0个0和0个1的字符串是0个
遍历顺序：和上面的01背包一致
题目特点：这里的物品是每一个字符串，背包是m个0和n个1的背包，这个背包不是之前只考虑物品的重量属性了，需要考虑物品的两个属性才能装入这个背包。动图效果多理解下
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
dp = [[0 for x in range(n + 1)] for y in range(m + 1)]
for w in strs:
m_sum = w.count("0")
n_sum = w.count("1")
for i in range(m, m_sum - 1, -1):
for j in range(n, n_sum - 1, -1):
dp[i][j] = max(dp[i][j], dp[i - m_sum][j - n_sum] + 1)
return dp[-1][-1]
LeetCode地址： 力扣
题目：给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
思路：将这些nums的元素当做物品，重量=价值=nums对应元素的值，背包假设为nums的和sum(nums)的一半
转化为：背包容量sum(nums)/2，是否有恰好装满的情况（装满了，剩下的一半也是剩下物品的重量了）
递推公式： dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]) （一维）
dp[i][j] = max(dp[i-1][j], dp[i-1][j - nums[i]] + nums[i]) （二维）
初始化：初始值都为0
遍历顺序：和上面的01背包一致
LeetCode地址： 力扣
题目：
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。思路：可以转化为分割等和⼦集的问题，target=total//2
不同点：（1）total不能等分的特殊情况不用处理
（2）子集问题中dp[-1]==target，
这里(total -dp[-1]) -dp[-1],含义将total分2份，一份是dp[-1]，一份是total-dp[-1]，他们差就是击碎后的最小值了，不理解我们在分析下，(total -dp[-1]) -dp[-1] === 2(target -dp[-1])，这个式子是不是target和dp[-1]的值越相近那结果是不是越小？dp[-1]如果等于target就是等分子集了，是不是就是完美粉碎了？如果还不理解dp[-1]的意义，那就在讲，转化01背包问题：target是一个背包，装石头或者上面等分子集的nums的元素，石头重量即是价值，这样取如何装找到最大价值
递推公式： dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]) （一维）
dp[i][j] = max(dp[i-1][j], dp[i-1][j - nums[i-1]] + nums[i-1]) （二维）
初始化：初始值都为0
遍历顺序：和上面的01背包一致
def lastStoneWeightII(self, stones: List[int]) -> int: """一维数组dp解法""" total = sum(stones) target = total // 2 dp = [0] * (target + 1) for i in range(len(stones)): for j in range(target, stones[i] - 1, -1): dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]) return total- dp[-1] - dp[-1] def lastStoneWeightII(self, stones: List[int]) -> int: """二维数组dp解法""" total = sum(stones) target = total // 2 dp = [[0 for x in range(target + 1)] for y in range(len(stones)+1)] for i in range(1, len(stones)+1): for j in range(1, target+1): if j < stones[i-1]: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j], dp[i-1][j - stones[i-1]] + stones[i-1]) return total- dp[-1][-1] - dp[-1][-1]
（3）目标和
LeetCode地址： 力扣
题目：
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
思路：每个元素有正负的两种情况，是否也是和分割等和⼦集、最后⼀块⽯头的重量 II问题类似，都是将nums分成两份，一份装，一份不装入，装入的是正号，不装入的是负号，是不是也像粉碎石头了？
不同点：这个背包的容量是多少呢？分隔等和子集的背包容量是total的一半，这里呢？一份正数和、一份负数和
正数和 + 负数和 = total
正数和 - 负数和 = target
正数和 = （total + target）/ 2
所以就转化为了正数和的表达式 的数目
递推公式： dp[j] = dp[j]+dp[j - nums[i]] （一维）
dp[i][j] = dp[i-1][j]+dp[i-1][j - nums[i-1]] （二维）
初始化：dp[0] =1、dp[i][0]=0 这个是二维的情况
遍历顺序：和上面的01背包一致
def findTargetSumWays(self, nums: List[int], target: int) -> int:
# 二维数组dp解法
total = sum(nums)
if target > total or (target + total) % 2 != 0 or target < -total:
# 特殊情况处理：target不能大于total,小于-total,如果功能不能整除2，就得不到正数和的部分
return 0
bag_size = (target + total) // 2
dp = [[0 for x in range(bag_size + 1)] for y in range(len(nums) + 1)]
#初始化
for z in range(len(nums)+1):
dp[z][0] = 1
for i in range(1, len(nums)+1):
for j in range(0, bag_size+1): # 这个变量背包从0开始，这里的0有具体的含义了，之前价值0是无意义的了
if j < nums[i-1]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i-1][j - nums[i-1]] + dp[i-1][j]
return dp[-1][-1]
def findTargetSumWays(self, nums: List[int], target: int) -> int:
# 一维数组dp解法
total = sum(nums)
if target > total or (target + total) % 2 != 0 or target < -total:
# 特殊情况处理：target不能大于total,小于-total,如果功能不能整除2，就得不到正数和的部分
return 0
bag_size = (target + total) // 2
dp = [0] * (bag_size + 1)
dp[0] = 1
for i in range(len(nums)):
for j in range(bag_size, nums[i] - 1, -1):
dp[j] = dp[j] + dp[j - nums[i]]
return dp[-1]
（4）一和零
题目链接：474. 一和零
题目：
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
思路：
dp[i][j]的含义：i个0和j个1组成的最大子集长度
递推公式： dp[i][j] = max(dp[i][j], dp[i - m_sum][j - n_sum] + 1)
初始化：0，组成0个0和0个1的字符串是0个
遍历顺序：和上面的01背包一致
题目特点：这里的物品是每一个字符串，背包是m个0和n个1的背包，这个背包不是之前只考虑物品的重量属性了，需要考虑物品的两个属性才能装入这个背包。动图效果多理解下
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
dp = [[0 for x in range(n + 1)] for y in range(m + 1)]
for w in strs:
m_sum = w.count("0")
n_sum = w.count("1")
for i in range(m, m_sum - 1, -1):
for j in range(n, n_sum - 1, -1):
dp[i][j] = max(dp[i][j], dp[i - m_sum][j - n_sum] + 1)
return dp[-1][-1]
LeetCode地址： 力扣
题目：
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
思路：每个元素有正负的两种情况，是否也是和分割等和⼦集、最后⼀块⽯头的重量 II问题类似，都是将nums分成两份，一份装，一份不装入，装入的是正号，不装入的是负号，是不是也像粉碎石头了？
不同点：这个背包的容量是多少呢？分隔等和子集的背包容量是total的一半，这里呢？一份正数和、一份负数和
正数和 + 负数和 = total
正数和 - 负数和 = target
正数和 = （total + target）/ 2
所以就转化为了正数和的表达式 的数目
递推公式： dp[j] = dp[j]+dp[j - nums[i]] （一维）
dp[i][j] = dp[i-1][j]+dp[i-1][j - nums[i-1]] （二维）
初始化：dp[0] =1、dp[i][0]=0 这个是二维的情况
遍历顺序：和上面的01背包一致
题目链接：474. 一和零
题目：
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
思路：
dp[i][j]的含义：i个0和j个1组成的最大子集长度
递推公式： dp[i][j] = max(dp[i][j], dp[i - m_sum][j - n_sum] + 1)
初始化：0，组成0个0和0个1的字符串是0个
遍历顺序：和上面的01背包一致
题目特点：这里的物品是每一个字符串，背包是m个0和n个1的背包，这个背包不是之前只考虑物品的重量属性了，需要考虑物品的两个属性才能装入这个背包。动图效果多理解下
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
dp = [[0 for x in range(n + 1)] for y in range(m + 1)]
for w in strs:
m_sum = w.count("0")
n_sum = w.count("1")
for i in range(m, m_sum - 1, -1):
for j in range(n, n_sum - 1, -1):
dp[i][j] = max(dp[i][j], dp[i - m_sum][j - n_sum] + 1)
return dp[-1][-1]
类似面试题目（360的题）：
有彩色粉笔m个，白色粉笔n个。
a个彩色粉笔+b个白色粉笔可以打包卖x元；
c个彩色粉笔打包卖y元；
d个白色粉笔打包卖z元。
问粉笔不一定用完，得到的最多价钱是多少？举例
输入：
m=5, n=5, a=1, b=2, c=3, d=3, x=2, y=1, z=3,
输出：
6
# 第一种：dp动态规划
def chalk1(m, n, a, b, c, d, x, y, z):
# dp[i][j]表示i个彩色粉笔和j个白色粉笔的最大价值
dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
# 物品做一个数据结构，方便下面遍历物品
temp = {(a, b): x, (c, 0): y, (0, d): z}
for temp_m, temp_n in temp:
for i in range(m, temp_m - 1, -1):
for j in range(n, temp_n - 1, -1):
# 递推公式和零和一的题目一模一样，寻找不装temp这个物品的最大价值+temp物品的价值
dp[i][j] = max(dp[i][j], dp[i - temp_m][j - temp_n] + temp[(temp_m, temp_n)])
return dp[-1][-1]
#第二种：递归
def chalk2(m, n, a, b, c, d, x, y, z):
res={} #这里放所有购买的彩色和白色粉笔的总数组合
def temp(m, n): # 此方法就是寻找m,n的不同组合的价值是多少
if (m, n) not in res:
r = 0
# 找到三种购买方式的最大价值
if m >= a and n >= b:
r = max(r, temp(m - a, n - b) + x)
if m >= c:
r = max(r, temp(m - c, n) + y)
if n >= d:
r = max(r,temp(m, n - d) + z)
res[(m, n)] = r
return res[(m, n)]
return temp(m, n)
#第三种：递归，相比较第二种，没有创建递归子函数
def chalk3(m, n, a, b, c, d, x, y, z):
res={}
if (m, n) not in res:
r = 0
if m >= a and n >= b:
r = max(r, chalk3(m - a, n - b, a, b, c, d, x, y, z) + x)
if m >= c:
r = max(r, chalk3(m - c, n, a, b, c, d, x, y, z) + y)
if n >= d:
r = max(r, chalk3(m, n - d, a, b, c, d, x, y, z) + z)
res[(m, n)] = r
return res[(m, n)]
7、完全背包
（1）零钱兑换II
（2）377题：组合总和IV
（3）322题：零钱兑换
（4）279题：完全平方数
（5）139题：单词拆分
8、多重背包
（1）打家劫舍
（2）打家劫舍II
（3）打家劫舍III
（4）买卖股票的最佳时机
（5）买卖股票的最佳时机II
（6）买卖股票的最佳时机III
（7）买卖股票的最佳时机IV
（8）最佳买卖股票时机含冷冻期
（9）买卖股票的最佳时机含⼿续费
（10）最⻓递增⼦序列
（11）最⻓连续递增序列
（12）最⻓重复⼦数组
3. 无重复字符的最长子串有点反义的题目3. 无重复字符的最长子串
def lengthOfLongestSubstring(self, s: str) -> int:
n, max_n, temp = 0, 0, ""
for i in s:
if i not in temp:
temp += i
n += 1
else:
if n > max_n:
max_n = n
pos = temp.index(i)
temp = temp[pos+1:] + i
n = len(temp)
if n > max_n:
max_n = n
return max_n
（13）最⻓公共⼦序列
（14）不相交的线
（15）最⼤⼦序和
（16）判断⼦序列
（17）不同的⼦序列
（18）两个字符串的删除操作
（19）编辑距离
（20）回⽂⼦串
（21）最⻓回⽂⼦序列
（2）377题：组合总和IV
（3）322题：零钱兑换
（4）279题：完全平方数
（5）139题：单词拆分
8、多重背包
（1）打家劫舍
（2）打家劫舍II
（3）打家劫舍III
（4）买卖股票的最佳时机
（5）买卖股票的最佳时机II
（6）买卖股票的最佳时机III
（7）买卖股票的最佳时机IV
（8）最佳买卖股票时机含冷冻期
（9）买卖股票的最佳时机含⼿续费
（10）最⻓递增⼦序列
（11）最⻓连续递增序列
（12）最⻓重复⼦数组
3. 无重复字符的最长子串有点反义的题目3. 无重复字符的最长子串
def lengthOfLongestSubstring(self, s: str) -> int:
n, max_n, temp = 0, 0, ""
for i in s:
if i not in temp:
temp += i
n += 1
else:
if n > max_n:
max_n = n
pos = temp.index(i)
temp = temp[pos+1:] + i
n = len(temp)
if n > max_n:
max_n = n
return max_n
（13）最⻓公共⼦序列
（14）不相交的线
（15）最⼤⼦序和
（16）判断⼦序列
（17）不同的⼦序列
（18）两个字符串的删除操作
（19）编辑距离
（20）回⽂⼦串
（21）最⻓回⽂⼦序列
（4）279题：完全平方数
（5）139题：单词拆分
8、多重背包
（1）打家劫舍
（2）打家劫舍II
（3）打家劫舍III
（4）买卖股票的最佳时机
（5）买卖股票的最佳时机II
（6）买卖股票的最佳时机III
（7）买卖股票的最佳时机IV
（8）最佳买卖股票时机含冷冻期
（9）买卖股票的最佳时机含⼿续费
（10）最⻓递增⼦序列
（11）最⻓连续递增序列
（12）最⻓重复⼦数组
3. 无重复字符的最长子串有点反义的题目3. 无重复字符的最长子串
def lengthOfLongestSubstring(self, s: str) -> int:
n, max_n, temp = 0, 0, ""
for i in s:
if i not in temp:
temp += i
n += 1
else:
if n > max_n:
max_n = n
pos = temp.index(i)
temp = temp[pos+1:] + i
n = len(temp)
if n > max_n:
max_n = n
return max_n
（13）最⻓公共⼦序列
（14）不相交的线
（15）最⼤⼦序和
（16）判断⼦序列
（17）不同的⼦序列
（18）两个字符串的删除操作
（19）编辑距离
（20）回⽂⼦串
（21）最⻓回⽂⼦序列
8、多重背包
（1）打家劫舍
（2）打家劫舍II
（3）打家劫舍III
（4）买卖股票的最佳时机
（5）买卖股票的最佳时机II
（6）买卖股票的最佳时机III
（7）买卖股票的最佳时机IV
（8）最佳买卖股票时机含冷冻期
（9）买卖股票的最佳时机含⼿续费
（10）最⻓递增⼦序列
（11）最⻓连续递增序列
（12）最⻓重复⼦数组
3. 无重复字符的最长子串有点反义的题目3. 无重复字符的最长子串
def lengthOfLongestSubstring(self, s: str) -> int:
n, max_n, temp = 0, 0, ""
for i in s:
if i not in temp:
temp += i
n += 1
else:
if n > max_n:
max_n = n
pos = temp.index(i)
temp = temp[pos+1:] + i
n = len(temp)
if n > max_n:
max_n = n
return max_n
（13）最⻓公共⼦序列
（14）不相交的线
（15）最⼤⼦序和
（16）判断⼦序列
（17）不同的⼦序列
（18）两个字符串的删除操作
（19）编辑距离
（20）回⽂⼦串
（21）最⻓回⽂⼦序列
3. 无重复字符的最长子串有点反义的题目3. 无重复字符的最长子串
def lengthOfLongestSubstring(self, s: str) -> int:
n, max_n, temp = 0, 0, ""
for i in s:
if i not in temp:
temp += i
n += 1
else:
if n > max_n:
max_n = n
pos = temp.index(i)
temp = temp[pos+1:] + i
n = len(temp)
if n > max_n:
max_n = n
return max_n
