动态规划是一种分治(Divide&Conquer)的思想。在将大问题化解为小问题的分治过程中，保存对这些小问题已经处理好的结果，并供后面处理更大规模的问题时直接使用这些结果。
适用于动态规划的问题，需要满足最优子结构和无后效性两种情况。
- 最优子结构性即如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。
- 无后效性即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
动态规划最重要的两个要点在于找到状态和状态转移方程，也就是递推关系。
如果不记录每一步的结果，动态规划的时间复杂度与Brute Force无异。动态规划实质上是一种以空间换时间的方法，通过存储过程中每一步骤的状态来降低时间复杂度。
举个栗子
我们以Leetcode的Climbing Stairs题目为例：
当前位置为第i级台阶时，有两种途径到达当前的状态：
- 从第
i-1级台阶走一步而来 - 从第
i-2级台阶走两步而来
因此，到达第i级台阶的途径为到达第i-1级台阶和到达第i-2级台阶的途径数量之和。我们可以得出如下的状态转移方程：
dp[i] = dp[i−1] + dp[i−2]
按照上面的状态向下递归，得到初始状态：
dp[3] = dp[1] + dp[2]
将dp[1]视为第一级台阶，有一种途径可以到达（从0走一步）
将dp[2]视为第二级台阶，有两种途径可以到达（从0走两步或者走两个一步）
因此初始状态如下
dp[0] = 0
dp[1] = 1
dp[2] = 2
按照状态转移方程求解dp[n]即可。
我的解法和笔记如下：https://nyan.im/posts/4078.html#Climbing%20Stairs(Easy)
发表回复/Leave a Reply