1. ：不同路径 II
题目链接: 63. 不同路径 II - 力扣（LeetCode）
应用条件：动态规划
难点：
# 确定dp数组（dp table）以及下标的含义：dp[i][j]表示有多少种方法到格子（i，j）
# 确定递推公式: dp[i][j] = dp[i-1][j] + dp[i][j-1]
# dp数组如何初始化: dp[0][i] = 1 dp[i][0] = 1,在有障碍物的地方都是0，并且dp[0][i]和dp[i][0]在i==0后面所有都是0
# 确定遍历顺序: for i in range(1,m): for j in range(1,n):
# 举例推导dp数组: dp[3][7] = dp[2][7] + dp[3][6]
个人错误：
思路：
class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:if obstacleGrid[0][0] == 1:return 0dp = [[0]*len(obstacleGrid[0]) for i in range(len(obstacleGrid))]for i in range(len(obstacleGrid[0])):if obstacleGrid[0][i] == 1:dp[0][i] = 0if i+1 < len(obstacleGrid[0]):for j in range(i+1,len(obstacleGrid[0])):dp[0][j] = 0breakelse:dp[0][i] = 1for i in range(len(obstacleGrid)):if obstacleGrid[i][0] == 1:dp[i][0] = 0if i+1 < len(obstacleGrid):for j in range(i+1,len(obstacleGrid)):dp[j][0] = 0breakelse:dp[i][0] = 1 for i in range(1,len(obstacleGrid)):for j in range(1,len(obstacleGrid[0])):if obstacleGrid[i][j] == 1:dp[i][j] = 0else:dp[i][j] = dp[i-1][j] + dp[i][j-1]print(dp)return dp[len(obstacleGrid)-1][len(obstacleGrid[0])-1] 2. ：整数拆分
题目链接: 343. 整数拆分 - 力扣（LeetCode）
应用条件：动态规划
难点：
# 确定dp数组（dp table）以及下标的含义：dp[i]表示拆分正整数i得到的最大乘积
# 确定递推公式: 把i拆分成j和i-j dp[i]=max(dp[i],j*(i-j),j*dp[i-j])
# dp数组如何初始化: dp[0]和dp[1]都是没有意义的，所以从2开始dp[2] = 1
# 确定遍历顺序: for i in range(3,n): for j in range(1,i):
# 举例推导dp数组: dp[5] = max(dp[i],j*(i-j),j*dp[i-j])
个人错误：
思路：
class Solution:def integerBreak(self, n: int) -> int:dp = [0]*(n+1)dp[2] = 1if n <2:return 0if n == 2:return 1for i in range(3,n+1):for j in range(1,i):dp[i] = max(dp[i],j*(i-j),j*dp[i-j])return dp[n]
3. ：不同的二叉搜索树
题目链接: 96. 不同的二叉搜索树 - 力扣（LeetCode）
应用条件：动态规划
难点：
# 确定dp数组（dp table）以及下标的含义：dp[i]表示i个节点得到的最多二叉搜索树
# 确定递推公式: 用j从1遍历i，表示把j当作头节点的二叉搜索树，dp[i] += dp[j-1]*dp[i-j]
# dp数组如何初始化: dp[0]和dp[1]都是1
# 确定遍历顺序: for i in range(2,n): for j in range(1,i):
# 举例推导dp数组: dp[5] += dp[j-1]*dp[5-j]
个人错误：
思路：
class Solution:def numTrees(self, n: int) -> int:dp = [0]*(n+1)dp[0] = 1dp[1] = 1if n<2:return 1for i in range(2,n+1):for j in range(1,i+1):dp[i] += dp[j-1]*dp[i-j]# print(dp)return dp[n]
4. ：01背包理论基础
题目链接:
应用条件：
难点：
# 确定dp数组（dp table）以及下标的含义：dp[i][j]表示从0-i物品中任取放入容量为j的背包中
# 确定递推公式: 就看这个物品(重量weight[i])放不放进背包里，放不进去直接dp[i][j] = dp[i-1][j] 能放进去看放进去价值大还是不放进去价值大dp[i][j] = max( dp[i-1][j], dp[i-1][j-weight[i]] +value[i])
# dp数组如何初始化: dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品
# 确定遍历顺序: 先遍历物品，然后遍历背包重量
个人错误：
思路：
n, bagweight = map(int, input().split())weight = list(map(int, input().split()))
value = list(map(int, input().split()))dp = [[0] * (bagweight + 1) for _ in range(n)]for j in range(weight[0], bagweight + 1):dp[0][j] = value[0]for i in range(1, n):for j in range(bagweight + 1):if j < weight[i]:dp[i][j] = dp[i - 1][j]else:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])print(dp[n - 1][bagweight])