​
​

活动地址：CSDN21天学习挑战赛

---

前言

提示：这里可以添加本文要记录的大概内容：

感觉大厂非常钟情于dp算法的考察，那我们就来复习一下呗，这些东西好久没碰过了，慢慢捡起来吧，今天先简要看看基本概念

---

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，而我们希望找到具有最优值的解。动态规划算法与分治法类似，基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

动态规划问题经分解得到的子问题往往不是互相独立的。需要保存已解决的子问题的答案，而在需要时再找出已保存的答案，这样就可以避免大量的重复计算。可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。

动态规划有两个重要的概念：
…

• 状态：解决某一问题的中间结果，它是子问题的一个抽象定义。
• 状态转移方程：状态与状态之间的递推关系。

动态规划解题步骤：
…

• 状态定义：找出子问题抽象定义。
• 确定状态转移方程：找出状态与状态之间的递推关系。
• 初始状态和边界情况：最简单的子问题的结果，也是程序的出口条件 。
• 返回值：对于简单问题，返回值可能就是最终状态；对于复杂问题可能还需对最终状态做一些额外处理。

下面就通过爬楼梯问题来看看动态规划的具体应用。

70. 爬楼梯

题目描述：假设正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？其中 n 是一个正整数。

本题大家如果没有接触过的话，会感觉比较难，多举几个例子，就可以发现其规律。

爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。

那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。

所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来，那么就可以想到动态规划了。

这道题有两个关键特征：

• 要求给出达成某个目的的解法个数；
• 不要求给出每一种解法对应的具体路径。

对于这个问题，每次爬楼梯只有两种情况：

最后一步爬 1 级台阶，前面有 n - 1 级台阶，这种情况下共有f(n - 1)种方法；
最后一步爬 2 级台阶，前面有 n - 2 级台阶，这种情况下共有f(n - 2)种方法；

f(n) 为以上两种情况之和，即 f(n)=f(n-1)+f(n-2)，这就是本题用到的递推关系。下面就根据动态规划的四个步骤来看那一下：

• 状态定义：初始化一个f数组，f[i]表示爬到i级台阶的方法数量；
• 状态转移方程：f(n)=f(n-1)+f(n-2)；
• 初始状态：一级台阶时，共1种爬法；两级台阶时，可以一级一级爬，也可以一次爬两级，共有2种爬法。即f[1] = 1，f[2] = 2；
• 返回值：f[n] ，即 n 级台阶共有多少种爬法。

动态规划实现代码如下：

/**
* @param {number} n
* @return {number}
*/
const climbStairs = function(n) {
    // 初始化状态数组
    const f = [];
    // 初始化已知值
    f[1] = 1;
    f[2] = 2;
    // 动态更新每一层楼梯对应的结果
    for(let i = 3;i <= n;i++){
        f[i] = f[i-2] + f[i-1];
    }
    // 返回目标值
    return f[n];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

上面用动态规划的思想解决了爬楼梯的问题，当然我们的目的并不是为了解决这个问题，而是通过这个问题来看动态规划，下面就来重新认识一下动态规划。

动态规划的思想和“分治”有点相似（把一个问题分解为相互独立的子问题，逐个解决子问题后，再组合子问题的答案，就得到了问题的最终解）。不同之处在于，“分治”思想中，各个子问题之间是独立的：比如说归并排序中，子数组之间的排序并不互相影响。而动态规划划分出的子问题，往往是相互依赖、相互影响的。

那什么样的题应该用动态规划来做？要抓以下关键特征：

• 最优子结构，它指的是问题的最优解包含着子问题的最优解——不管前面的决策如何，此后的状态必须是基于当前状态（由上次决策产生）的最优决策。就这道题来说，f(n)和f(n-1)、f(n-2)之间的关系（状态转移方程）印证了这一点。
• 重叠子问题，在递归的过程中，出现了反复计算的情况。
• 无后效性，无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。

所以，只要需要解决的问题符合这三个关键特征，就可以使用动态规划来求解。

---

​