• 设计动态规划算法时，需要确认:
  1. 原问题与子问题
  2. 动态规划状态
  3. 边界状态结值
  4. 状态转移方程

• 在爬楼梯时，每次可向上走1阶台阶或2阶台阶，问有n阶楼 梯有多少种上楼的方式? dp[n] = dp[n-1] + dp[n-2]

• 由于同时从相邻的两个房屋中盗取财宝就会触发报警器，故: a.若选择第i个房间盗取财宝，就一定不能选择第i-1个房间盗取财宝; b.若不选择第i个房间盗取财宝，则相当于只考虑前i-1个房间盗取财宝;

1.确认原问题与子问题: 原问题为求n个房间的最优解，子问题为求前1个 房间、前2个房间、...、前n-1个房间的最优解。

2.确认状态: 第i个状态即为前i个房间能够获得的最大财宝(最优解)。

3.确认边界状态的值: 前1个房间的最优解，第1个房间的财宝; 前2个房间的最优解，第1、2个房间中较大财宝的。

4.确定状态转移方程: a.选择第i个房间:第i个房间+前i-2个房间的最优解 b.不选择第i个房间:前i-1个房间的最优解 动态规划转移方程: dp[i] = max(dp[i-1], dp[i-2] + nums[i]); (i>=3)

• 题目描述：给定一个数组，求这个数组的连续子数组中，最大的那一段的和。

• 若假设第i个状态(dp[i])代表前i个数字组成的连续的最大子段和，能否推导出dp[i]与 dp[i-1]之间的关系呢? 由于有不相邻的条件，这里需要作修改：第i个状态(dp[i])即为以第i个数字结尾的最大子段和(最优解)。以第i-1个数字结尾的最大子段和(dp[i-1])与nums[i]相邻。

1. 确认原问题与子问题： 原问题为求长度为n的数值，最大子段的和

2. 确认状态： dp[0..n-1]中最大值为最优解

3. 确认边界值： 第1个的最优解为num[0]，第二个为dp[0]+nums[1]和nums[1]中较大者。以此类推dp[i]为dp[i-1]+nums[i]和nums[i]中的较大者。

4. 确定状态转移方程：dp[i] = max(dp[i-1]+nums[i], nums[i]);

   1. 与i-1相邻
   2. 与i-1不相邻

• 动态规划，dp[n] = min(dp[n-coins[1..m]]) + 1, 其中n范围在0...amount, 时间复杂度O(amount*m),空间复杂度O(amount)

1. 确认原问题与子问题： 原问题为amount最少需要多少次，子问题为之前已经求解出amount-1之前的最少需要兑换的次数

2. 确认状态： dp[amount]为当前状态的最优解

3. 确认边界值 dp[0] = 0表示不需要兑换就可以得到次数

4. 确定状态转移方程：dp[n] = min(dp[n-coins[1..m]]) + 1