动态规划算法

动态规划是一种分治(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://blog.nyan.im/posts/4078.html#Climbing%20Stairs(Easy)

参考资料

算法-动态规划 Dynamic Programming–从菜鸟到老鸟 – 有图有真相 – CSDN博客

动态规划 · 笔试面试知识整理

Show CommentsClose Comments

2 Comments

Leave a comment