动态规划

ryluo 2020-06-24 23:01:44

动态规划本质是通过历史记录来避免我们的重复计算,而这些历史记录需要通过一维数组或者二维数组保存下来。

动态规划的三个步骤:

  1. 定义数组元素的含义:要求什么就定义什么
  2. 找出数组之间的关系:当要计算dp[n]时,可以利用dp[n-1],dp[n-2],……dp[1]推算出dp[n],也就是可以利用历史数据推算出新的元素值,所以需要找出数组元素之间的关系。例如:dp[n]=dp[n-1]+dp[n-2],这就是一种递推关系
  3. 找出初始值:因为是递推关系,所以就必须要有初始值,而在动态规划中的初始值主要根据问题来,比如有时候只需要有dp[1]就够了,有时候需要dp[1], dp[2]等。找初始值的时候一定不要找漏了


案例1:简单的一维DP

问题描述:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

dp[i] 表示青蛙跳上一个n级台阶总共的跳法

dp[i] = dp[i-1] + dp[i-2]

dp[0] = 0;
dp[1] = 1;
dp[2] = dp[0] + dp[1] = 1 ?      dp[2] = 2
dp[3] = dp[1] + dp[2] = 3

参考资料:

https://zhuanlan.zhihu.com/p/91582909