算法---动态规划（持续更新学习）

1.动态规划的经典问题

（1）动规基础：爬楼梯、斐波那契数列
（2）背包问题：0-1背包，多重背包
（3）打家劫舍
（4）股票问题
（5）子序列问题

2.动态规划的思路流程

（1）dp数据定义和下标的定义
（2）递推公式
（3）dp数组如何初始化
（4）遍历顺序
（5）打印顺序

3.0-1背包

（1）0-1背包，有n种物品，每种物品都只有1个，每个物品有自己的重量和价值，有一个重量为m的背包，问这个背包最多能装价值为多少的物品。
物品0 1 （重量） 15（价值）
物品1 3 （重量） 40（价值）
物品2 4 （重量） 30（价值）
背包最大重量是4。
装满这个背包的最大价值是？
1）dp数组定义和下标定义
dp[i][j],编号下标为[0,i]的物品放进容量为j的背包里。
2）递推公式
dp[i][j]可以从哪几个方向推导出来
dp[i-1][j]：不放物品i
dp[i-1][j-weight[i]]+value[i] ：放物品i(不放物品i背包的最大价值：背包的容量-放物品i的重量）
dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]+value)
3）dp数组如何初始化
正常的初始化是

当背包容量是0的时候，物品0、物品1、物品2都不能放入到背包中。我们假设物品0的重量是2，索引当背包容量是0和背包容量是1的时候物品都放不来，使用前两列第一行初始化为0。

4）遍历顺序
对于二维数组的0-1背包问题，可以颠倒两个for循环的顺序，先遍历背包和先遍历物品都是没差别的。因为取一个元素，当前元素都是由正上方和左上方推导出来。
5）打印顺序