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）打印順序