动态规划
动规的五部曲:
- 确定dp数组(dp table)以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
509.斐波那契数列
70.爬楼梯
746.使用最小花费爬楼梯
62.不同路径
63.不同路径II
343.整数拆分
96.不同的二叉搜索树
本轮树可以分为当1,2,3…n当根节点时,有左子树形式*右子树形式种形式,然后相加
K46.携带研究材料
01背包问题
-
dp[i][j]代表从0-i中挑选物品放到j大小的背包里最大的value 行是物品,列是背包大小。
注意dp数组的大小,dp[m][n+1] -
转化为一维数组时,先遍历物品,再遍历包的大小,对于包大小的遍历应该从大到小,避免重复放进物品。
416.分割等和子集
转化为01背包问题,只需要检查能不能拼凑到sum/2大的背包即可,value和weight都是数值