参考：https://cloud.tencent.com/developer/article/1692068
热身
斐波那契数列
递归求解
自顶向下，存在大量的重复计算
动态规划
保存中间状态，利用保存的历史状态求解问题，减少了重复计算，空间换时间。
空间复杂度优化
只需借助两个变量dp1、dp2
解题步骤：
步骤一：定义dp数组的含义
步骤二：定义状态转移方程
步骤三：初始化过程转移的初始值
步骤四：可优化点(可选)
198. 打家劫舍
-
dp[i]：到第i户时，抢得最大金额
-
状态转移方程
-
偷第i户
不能连着偷，
dp[i] = dp[i-2] + nums[i-1]，此处用i-1是因为第i户，抢得金额刚好对应的nums[i-1] -
不偷第i户
dp[i] = dp[i-1]
综上
dp[i] = max(dp[i-2] + nums[i-1], dp[i-1]) -
-
初始值
dp[0] = 0 // 还没开始偷 dp[1] = nums[0] // 到了第1户直接偷
62. 不同路径
-
dp(i,j)
走到（i，j）处的不同路径数
-
状态转移方程
只能向下或向右走，到达（i，j）位置，要么从上面的位置（i-1，j）处来，要么从左边得位置（i，j-1）处来
dp(i,j) = dp(i-1,j) + dp(i,j-1) -
初始值
dp(0,0) = 1
第一行的所有位置（0，i），只能由起始点向右走，只有一种路径；同理，第一列的位置（i，0），只能由起始点向下走，也都只有一种路径。
63. 不同路径 II
路径上有障碍物
-
dp(i,j)
走到（i，j）处的不同路径数
-
状态转移方程
-
没有障碍物的情况下
只能向下或向右走，到达（i，j）位置，要么从上面的位置（i-1，j）处来，要么从左边的位置（i，j-1）处来
dp(i,j) = dp(i-1,j) + dp(i,j-1) -
有障碍物
dp(i,j) = 0
-
-
初始值
第一行的所有位置，只要遇到一个障碍物，其后的所有都不可达，均置为0；第一列同理。
213. 打家劫舍 II
环形打家劫舍，首户和尾户不能同时抢
思路：
-
只有1户，直接抢即可
-
只有2户，抢最大金额即可
-
超过2户，需要考虑两者情况（抢首户 or 抢尾户），再取较大者
-
dp[i]
表示抢第i户所得最大金额
-
状态转移方程
同打家劫舍Ⅰ
-
边界条件
dp[0] = 0;
dp[1] = nums[0]; //抢首户不抢尾户
dp[1] = nums[1]; //抢尾户不抢首户
337. 打家劫舍 III
子问题
树中每个节点都有 选 或 不选 两种选择。子问题subproblem定义为，子树根节点选的抢得最大金额 和 子树根节点不选的抢得最大金额；原问题的解就是 max(sub(根节点选), sub(根节点不选))
c++ 实现，二叉树后序遍历，用2个hash表存储，选或不选每个节点的子问题的解
定义f表存储选子树根节点的最优解，g表存储不选子树根节点的最优解
状态转移方程
-
f[t] = t->val + g[t->left] + g[t->right]
选子树根节点，则左右子节点均不能选
-
g[t] = max(f[t->left], g[t->left]) + max(f[t->right], g[t->right])
不选子树根节点，左子树根节点可选可不选，取最大值；右子树同理