秒懂算法 | DP概述和常见DP面试题

 动态（DP）是一种算法技术，它将大问题分解为更简单的子问题，对整体问题的最优解决方案取决于子问题的最优解决方案。本篇内容介绍了DP的概念和基本操作；DP的设计、方程推导、记忆化编码、递推编码、滚动数组以及常见的DP面试题。

01、DP概述

1. DP问题的特征

下面以斐波那契数为例说明DP的概念。斐波那契数列的每个数字是前面两个数字的和，前几个数是1、1、2、3、5、8。计算第n个斐波那契数，用递推公式进行计算：

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

用递归编程，代码如下。

int fib (int n){if (n == 1 || n == 2)return 1;return (fib (n -1) + fib (n -2));
}

为了解决总体问题fib(n)，将其分解为两个较小的子问题fib(n−1)和fib(n−2)。这就是DP的应用场景。

有一些问题有2个特征：重叠子问题、最优子结构。用DP可以高效率地处理具有这2个特征的问题。

（1）重叠子问题

首先，子问题是原大问题的小版本，计算步骤完全一样；其次，计算大问题的时候，需要多