0
动态规划算法
source link: https://nyan.im/p/dynamic-programming
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
动态规划算法
Frank
May 7, 2019
动态规划是一种分治(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)
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK