我正在参加「启航计划」

什么是动态规划？

 动态规划（dp）问题是经过求子问题解的办法，来处理本来杂乱或庞大的问题。
浅显的来讲，动态规划问题都能够用方程的形式进行表达，处理dp问题的要害也在于找出问题潜在的方程。 比方下图中，有一个机器人在m*n的网格的左上角，它要抵达右下角的目的地，但每一次只能向下或许向右走，你能算出有多少条不同的途径吗？

 这种问题运用暴力枚举在一些情况下或许也能处理，可是会花费很多的时间和耗费很多的内存。而且在力扣或牛客等，暴力法通常是不会ac的。

动态规划问题解法

首要，有两种办法：

1. 自下而上
2. 自上而下

1. 自下而上

自下而上是经过迭代 完成的：
自下而上便是先从子问题开始核算，重复核算推算出问题的解。

斐波那契数列[1、1、2、3、5、8、13、21、34、……]以如下递推的办法界说：
F(0)=0，F(1)=1,F(n)=F(n – 1)+F(n – 2)（n ≥ 2，n ∈ N*）
假如求F(n)的值，在已知F(0)=0, F(1)=1时，经过F(0)和F(1)核算F(2)，然后运用核算成果核算F(3)…
重复核算能够求解F(n)。

// 伪代码如下:
F = array of length (n + 1)
F[0] = 0
F[1] = 1
for i from 2 to n:
    F[i] = F[i - 1] + F[i - 2]

2. 自上而下

自上而下经过递归完成，而且经过 回忆化进步功率（其实便是递归+回忆化搜索）

持续以斐波那契数列的递推公式为例，假如咱们想求解F(n)，咱们需求求解F(n-1)和F(n-2)；求解F(n-1)需求F(n-2)和F(n-3) ，求解F(n-2)需求F(n-3) 和F(n-4)…一直递归到已知的F(0)=0和F(1)=1

自上而下的缺陷也很明显，在核算中存在了很多的重复核算，导致功率不高
处理办法也很简单，用空间换时间，也便是回忆化：将函数调用的成果存储在哈企图或数组中，这样当再次进行相同的函数调用时，咱们能够回来回忆的成果，防止重复核算。

//伪代码如下:
memo = hashmap
Function F(integer i):
    if i is 0 or 1: 
        return i
    if i doesn't exist in memo:
        memo[i] = F(i - 1) + F(i - 2)
    return memo[i]

总结

或许有人要问：“这两个办法哪个更好呢？”

动态规划问题能够用二者恣意一种办法完成，每个办法都有各自的长处:

• 自下而上的运转速度更快 (递归功率低)
• 自上而下的完成更简单 (运用递归，咱们不用在意子问题的逻辑次序；而自下而上的办法中，咱们需求处理子问题的逻辑次序)

 文章开头问题及图片的出处：《力扣 62.不同途径》，dp问题十分经典的一道标题，感兴趣的小伙伴能够测验一下。

祝你今天愉快，你明日的愉快藏着我明日再祝。——王小波