动态规划

解决动态规划题的思路分为两步：先想好了思路，再动手实现

确定状态转移方程其实就是一个关系，相同问题在不同规模下的关系，看起来很抽象对吧，简单来讲，就是通过总结的规律，推导出数学公式。

比如动态规划的入门题目，求斐波那契数列第n位的值，我们知道，斐波那契前七位如下:

shell

1 1 2 3 5 8 13

我们使者来找一下规律:

假设我们有个函数名叫 dp(n)

所以我们推导出下面规律:

dp(6) = dp(5) + dp(4)
dp(n) = dp(n - 1) + dp(n - 2)

dp(6) dp(5) dp(4) 是三个不同规模的问题,他们解决的是相同的问题,都是求斐波那契数列某一位的值, 但规模不一样。
所以 dp(6) dp(5) dp(4) 之间的关系我们称之为状态转移方程,也就是 dp(n) = dp(n - 1) + dp(n - 2)

然后，我们在确定状态转移方程的时候，往往需要考虑一些特殊解

dp(6) = dp(5) + dp(4)
dp(n) = dp(n - 1) + dp(n - 2)

// 考虑特殊解
dp(1) = 1
dp(2) = 1

斐波那契数列的动态转移方程

当 n > 2

dp(n) = dp(n - 1) + dp(n - 2)

当 n <= 2

dp(n) = 1

所以我们很容易能实现代码:

function dp(n) {
  // if (n === 1 || n === 2) return 1
  if (n <= 2) return 1
  return dp(n - 1) + dp(n - 2)
}

动态规划 ​