理论+实践，带你掌握动态规划法

摘要：本文介绍了动态规划法的基本概念，通过详细解析动态规划法的特征，给出判断问题是否使用动态规划法结题的思路。

本文分享自华为云社区《五大基础算法--动态规划法》，作者： 大金（内蒙的）。

一、基本概念

动态规划法，和分治法极其相似。区别就是，在求解子问题时，会保存该子问题的解，后面的子问题求解时，可以直接拿来计算。

专业的说法是：

对于一个规模为n的问题，将其分解为k个规模较小的子问题（阶段），按顺序求解子问题，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，通过决策求得局部最优解，依次解决各子问题。最后可以通过简单的判断，得到原问题的解。

说法有些晦涩难懂，我给大家解释下：

阶段：求解第n个子问题称为第n个阶段。动态规划是按照顺序去求解子问题的，这里子问题的求解顺序很重要。
状态：在求解第n个阶段时，已求解n-1个阶段的解，称为状态。
决策：在求解第n个阶段时，根据状态和计算规则，可以得到第n个阶段时解。

二、基本特征

动态规划法所能解决的问题一般具有以下几个特征：

1) 大问题可分解性

该问题可以分解为若干个规模较小的问题，即该问题具有最优子结构性质。

2) 子问题易解决性

该问题的规模缩小到一定的程度就可以容易地解决

3) 解可合并性

利用该问题分解出的子问题的解可以合并为该问题的解；

4) 子问题重叠性

当计算出某个子问题的解时，后续多个问题都需要计算该子问题的解，所以在计算某个子问题的解，将其保存，就节省了分治法重复计算的时间。

三、一些误解

1.状态转移方程

很多博客都说什么状态转移方程，感觉说的很高大上，一般解题上来就是状态转移方程是xxxx，代码是xxxx，翻译下是什么意思呢？
在求解第n个子问题的时候，通过已求解n-1个阶段的解和计算规则，可以得到第n个阶段时解。
即是最新的状态=目前的状态+决策。

2.初始化

很多题目解题的时候都说初始化，这并不是动态规划法的步骤。应该正确的去理解这些操作。动态规划在划分子问题求解顺序时，基本是先求解易求解最小的子问题，在由这些已经求解的阶段+计算规则，就能直接求得第n阶段的解。所以初始化的含义是，求得初始阶段的解。

3.边界条件

一般题目会说边界是啥，可以理解为怎么判断所有的子问题已经求解结束了。正常人也不会写while（true）吧，你总得让程序结束，判断你已经解决好这个问题了。

四、动态规划法的基本步骤

step1 分解：

将一个问题分解为多个子问题，需要注意子问题解决的顺序，应该先求解易求解的子问题，且后续的阶段可以通过前面的阶段+决策得到。

step2 状态转移：

通过得到的规律，写出状态转移方程。
第n阶段=当前状态+决策（前n个阶段解和计算规则）

step3 写代码：

将最先算的阶段计算出来，中间阶段通过状态转移方程计算状态，直到所有阶段计算结束。

step4 得到解：

所有阶段计算结束，可以通过简单的统计，例如Max，Min等遍历阶段的值，得到最后的解。

五、经典问题

好记性不如烂笔头，有一些适用动态规划法的问题，可以帮我们不断强化的解题思想。在解决问题时，希望大家可以注意判断题目的解决思路，看是否符合动态规划法的四个特征，这样不断强化，才能将算法掌握。

最长回文子串

下面附上我的题解：

点击关注，第一时间了解华为云新鲜技术~