动态规划的入门，一般是从斐波拉契数列开始。该数列由0和1开始，后面的每一项数字都是前面两项数字的和，定义如下：
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), 其中 n > 1
给定一个n，要求F(n)，用递归方法可以很容易地解决这个问题，代码如下：
def fib(self, n: int) -> int:
if n == 0 or n == 1:
return n
return fib(n-1) + fib(n-2)
然而，上面的递归方法会造成大量重复计算，因为有很多重复子问题，时间复杂度为O(2^n)。例如，在求f(5)时，需要先求子问题f(4)和f(3)。递归地求f(4)时，又要先求子问题f(3)和f(2)，这里的f(3)与求f(5)时的子问题就重复了。
为了解决这个问题，我们就想到一个方法：如果我们每次都把结果保存下来,复杂度就会大大降低。能不能让每个重复的子问题都只计算一次，即每个F(n)都只计算一次。这就是动态规划的核心思想：
- 将原问题分解成一系列子问题
- 每个子问题只求解一次，保存到一个状态数组
dp[]中
用动态规划来解斐波拉契数列：
def fib(self, n: int) -> int:
if n == 0 or n == 1:
return n
dp = [0] * (n+1)
dp[0] = 0
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
将时间复杂度由O(2^n)降低到了O(n)，真香！
如果看了上面的内容，你还是云里雾里，那么：
很正常
理解了dp的思想，也不一定会刷题，下面分享一套自己的刷题模板。首先来看一个经典的爬楼梯问题：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
前面说了动态规划的核心思想，是把一个问题分解成许多个不互相重合的子问题。对于这个爬楼梯问题，我们需要怎么开始分解呢？
一个很好的方法是，先找到最后一步的解决方法，即得到最终答案的前一步。对于这个例子，最后一步爬完楼梯之后会到达顶楼。那么要到达顶楼、最后一步应该是什么呢？
很显然，由于每次只能爬一个或者两个台阶，那么到达顶楼之前，要么在倒数第一层，最后爬一个台阶登顶。要么在倒数第二层，最后爬两个台阶登顶。这样问题就分解成了：
到达顶楼的方法 = 到达倒数第一层的方法 + 到达倒数第二层的方法
这样就可以自顶向下递推，用dp[i]来表示到达第i层的方法，写成伪代码：
dp[i] = dp[i-1] + dp[i-2]
这里再回顾一下前面，为什么递归的时间复杂度非常爆炸？
因为计算dp[i]的时候需要计算一次dp[i-2]，计算dp[i-1]的时候，由于dp[i-1] = dp[i-2] + dp[i-3]，也需要计算一次dp[i-2]，这里就重复了，学过编程的人都知道，递归里的重复是非常恐怖的。
回过来，dp[]数组叫做状态数组，目的是保存之前每一次计算的值。既然计算后面的值需要用到前面的值，那么就肯定是从前面开始计算，即自底向上。
到这里，大家都应该发现了，我们将问题从递归的自顶向下、变成了动态规划的自底向上，从而降低了复杂度。即：
递归 -> 动态规划
|| ||
自顶向下 -> 自底向上
那么爬楼梯问题的的动态规划解应该为：
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
dp = [0]*(n+1)
dp[0] = 0
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
