直接递归
带备忘录的递归（分治）
递推（动态规划）
分治递归与动态规划对比
分治法动态规划与的联系区别
联系：都是问题分解为子问题缩小规模来计算
区别：分治法的子问题是相互独立的，不包含公共子问题，适合自顶向下求解；动态规划的子问题是包含公共子问题的，适合递归定义最优值然后自下向上求解
动态规划的步骤：
1）找出最优解性质
2）递归定义最优值
3）自底向上求解
每种物品有限的背包问题
动态规划总结
完全背包问题
状态转移方程：
dp[i][j]=max{dp[i][j-v[i]]+c[i],dp[i-1][j]},v[i]<=j
dp[i][j]=dp[i-1][j],v[i]>j