动态规划算法模板：
[bash] 1 2 3 4 5 6 7 8 9 10 11 12 result = [] void dynamic_programming (路径, 选择列表) { vector<int > dp (容量 + 1 , base case1); dp[0 ][0 ][...] = base case2; for 状态1 的个数 for 状态2 的个数 for ... dp[状态1 ][状态2 ][...] = 求最值 or 求和(选择1 , 选择2 ，...); }
按照如下顺序刷力扣上的题目，相信会帮你在学习回溯算法的路上少走很多弯路。
509. 斐波那契数
1137. 第 N 个泰波那契数
70. 爬楼梯
746. 使用最小花费爬楼梯
198. 打家劫舍 ：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
213. 打家劫舍 II int res = max(helper(nums, 0, size - 2), helper(nums, 1, size - 1));
740. 删除并获得点数
55. 跳跃游戏
45. 跳跃游戏 II
53. 最大子序和 : dp[i]是以nums[i]结尾的最大自序和
918. 环形子数组的最大和
152. 乘积最大子数组
1567. 乘积为正数的最长子数组长度
1014. 最佳观光组合
121. 买卖股票的最佳时机
122. 买卖股票的最佳时机 II ：vector<vector> dp(n, vector(2, 0)); dp[i][1]表示第i天持有股票
309. 最佳买卖股票时机含冷冻期
714. 买卖股票的最佳时机含手续费
343. 整数拆分 ：dp[i]拆分数字能获得的最大乘积，dp[i]=max(j*i-j, j*dp[i-j])
剑指 Offer 14- I. 剪绳子
416. 分割等和子集 ：dp[i][j]表示下标[0, i]区间内是否能选出一些数使其之和恰好为j
139. 单词拆分
42. 接雨水
413. 等差数列划分
91. 解码方法
264. 丑数 II
96. 不同的二叉搜索树 :dp[i] = dp[]
118. 杨辉三角
119. 杨辉三角 II
931. 下降路径最小和
120. 三角形最小路径和
1314. 矩阵区域和
304. 二维区域和检索 - 矩阵不可变
62. 不同路径
63. 不同路径 II
64. 最小路径和
221. 最大正方形
5. 最长回文子串
516. 最长回文子序列
300. 最长递增子序列 ：dp[i] = max(dp[i], dp[j] + 1);
376. 摆动序列
392. 判断子序列
1143. 最长公共子序列
72. 编辑距离
322. 零钱兑换
518. 零钱兑换 II
377. 组合总和 Ⅳ
343. 整数拆分
279. 完全平方数