🍿本文主题：动态规划 🎈更多算法：回溯算法 💕我的主页：蓝色学者的主页

很开心又和大家见面了，今天我们来一起学习一下传说中的动态规划，通过两道很经典的动态规划题目，帮助大家快速的理解动态规划的思想（斐波那契数列、爬楼梯），之后我还会留下本节课的作业，感兴趣的话一起来看看吧~

动态规划（Dynamic Programming）是运筹学的一个分支，是求解决策过程最优化的过程。在初次见到动态规划的题目时，我们会听到诸如：状态转移方程、Dp数组等概念，我们就从这些概念入手，揭开动态规划的神秘面纱~

何为状态转移呢？我想让你思考一个问题：

求4！= ？ 注：[n！]指的是n的阶乘，例如 3！= 3 * 2 * 1

根据阶乘的定义，我们想到 4！= 4 * 3 * 2 * 1 = 24 再仔细观察一下，就会得出 4！= 4 * 3！

这样我们得出了一个结论：

要求[n]的阶乘，只需要求出[n-1]的阶乘，要求[n-1]的阶乘，只需要求出[n-2]的阶乘

这样我们就完成了一次状态转移，即：要求[n]的值，先去求[n-1]的值

理解了状态转移，我们再来看看Dp数组是什么，同样的，我们再思考一个问题：

为什么要有Dp数组？

不妨再去思考一下上面阶乘的问题，如果要求[4!]，我们需要什么呢？ 要求[4!]——需要先求[3!] 要求[3!]——需要先求[2!] 要求[2!]——需要先求[1!]

假如没有一个Dp数组，我们将之前的阶乘结果放到哪里去呢！ 在计算 [4!] 的时候，希望能够直接拿到 [3!],因此我们必须要把 [3!] 实现存入一个数组。

我们把这种存放前面状态的数组，叫做Dp数组，正是有这种数组帮助，我们才能省去很多繁琐的重复计算

题目链接：剑指offer-斐波那契数列 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。

斐波那契数列的定义如下： F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

根据本题对斐波那契数列的定义，我们知道第n项等于第n-1项加上第n-2项，与状态转移概念相符，因此本题我们可以使用动态规划来求解。

要求第n个斐波那契数，就要求第n-1个和第n-2的斐波那契数，因此我们的Dp数组就应该存放斐波那契数，注意，由于Dp(0)、Dp(1)没有前两个斐波那契数，因此我们要对这两个元素提前赋值。

Dp[0] = 0; Dp[1] = 1;

仔细观察状态转移，我们会发现与阶乘还不同的是，斐波那契数只依赖于前两个斐波那契数，因此我们可以将Dp数组优化成两个变量。

注：两者本质上都是动态规划的思路

纯动态规划代码：

题目链接：leetcode70 爬楼梯 假设你正在爬楼梯。需要 [n] 阶你才能到达楼顶。 每次你可以爬 [1] 或 [2] 个台阶。你有多少种不同的方法可以爬到楼顶呢？

根据题目要求，要爬到第n楼，有两种方法，也就是从[n-1]楼爬1步或者从[n-2]楼爬两步，我们肯定不是从底层直接到[n-1]、[n-2]楼的，那么这个问题就转换成了有多少种方法到[n-1]+有多少方法到[n-2]的一个问题了，这样我们就完成了状态转移的分析

要求到第[n]楼要爬多少台阶，Dp数组就是存放要爬多少台阶的数组，由于第一楼、第二楼没有前两楼，我们需要对其初始化：

Dp[1] = 1; Dp[2] = 1;