C++ 算法进阶系列之聊聊动态规划的两把刷子

1. 前言

和是算法界的两个扛把子，想进入算法之门，则必须理解、掌握这两种算法的本质。一旦参悟透这种算法的精髓，再加上对树、图等复杂数据结构的深入理解，可以解决大部分的算法问题。

本文通过几个典型案例，再次聊聊动态规划算法。其实动态规划算法也就 把刷子。

找到当前子问题的所有可选择项，在所有选择项中选择最大值或最小值。

此子问题的最优解，作为下一个子问题的可选择项。最终推导出最终结果。每一个子问题只需关心与其有依赖子问题的结果而无需关注其实现过程。

动态规划的基本理念：步步为营，每次选择最好，达到最终是最好的。

如下通过几个案例来理解动态规划如何步步为营。

2. 最多的

2.1 问题描述

现假设有一个特殊的键盘包含下面的按键：

：在屏幕上打印一个。

：：选中整个屏幕。

复制选中区域到缓冲区

将缓冲区内容输出到上次输入的结束位置，并显示在屏幕上。

现在，你只可以按键 次(使用上述四种按键) ，请问屏幕上最多可以显示几个 呢?

2.2  样例

2.2.1 样例

输入：3输出：解释：我们最多可以在屏幕上显示三个，通过如下顺序按键：

2.2.2 样例

输入：输出：解释：我们最多可以在屏幕上显示   个，通过如下顺序按键

2.3 问题解析

本题是求最值问题，可使用动态规划实现。如前所说，要使用动态规划算法，首先要知道对于每一个子问题而言有哪些选择项。

Tips：  于本题而言，不同的按键次数可以认为是一个个子问题。

在屏幕上输出，也就是让屏幕上的字符的个数发生变化，可以有种选择：

直接按下键。只需要一次按键就能输出｀Ａ｀。

复制屏幕上的。先按下，在缓冲区添加内容 ，然后可以重复按在屏幕上输出字母。

则在不同的按键次数下，哪一种选择最佳？

本题中动态规划算法要做的是：

由小规模状态下的积累得到到大规模状态下的结果。此题要计算的是当按键次数的变化下子母的个数。

当次数状态量发生变化后，需要选择出最理想方案。

解题流程：

可以先定义一个一维 数组。用来存储不同次数状态下子母的个数。

现分析在不同次数下，哪一种选择方案可得到最理想结果。

当按键次数为时。此状态下只可能通过按下键输出子母。

当按键次数为 时。也只能通过直接按下A键输出子母A，这时屏幕上的字母个数为 。

当按键次数为时。通过直接按｀A｀键，也可以通过复制输出A  。

直接按下键的个数为。

显然，直接按键输出的字母更多。在两个方案中选择直接按下子母键为最佳方案。

当按键次数为时。

直接按下键输入，此时屏幕上的字符为个。

使用复制方案在屏幕上输出时。复制方式有 种：

在数组位置处、在处。这样复制的是位置的子母个数。

在数组位置处、在位置处。这样复制的是位置的子母个数。

编码实现：

3.  最长递增子序列

3.1 问题描述

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入：

输出：

解释：最长的上升子序列是 ，它的长度是 。说明：可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。子序列和子串的区别，子串是连续的，子序列不一定是连续的。

###　3.2 问题分析

如何使用动态规划思想解决此问题。

创建一维动态数组。记录当数组中的数据规模变化时，其子序列的长度。初始值为 ，数列是自己的子序列。

从左向右扫描原始数组，扫描到数据 时，显然，其子序列的个数为 。

扫描到数据 时，将其和前面的 进行比较，因比其小，故不能为递增子序列做出贡献，保留原来子序列的个数。

扫描到时，其对应数组中的值为 。

扫描到时，其比小，但比大，可以成为以为当前状态值的递增子序列。

扫描到时，因只比大，此时最长子序列应该是以结束时的最长子序列加。

扫描到时，因 比都大，则需要在以结束时最长子序列中求最大值。动态规划的特点就是，状态的改变时，往往需要在多个选择中选择最佳的。

同理，当扫描到，因为它比前面的所有数字都大，则需要在已经填充的数组中找出最大值且再加 。

按相同的原理，最后 数组中的值应该如下所示。

3.3 编码实现

4. 最小路径和

4.1 问题描述

现有一个二维数组，其中的元素都是非负整数，现在你站在左上角，只能向右或者向下移动，需要到达右下角。现在请你计算，经过的路径和最小是多少？

二维数组如下图所示。

本题是典型的题型。

基本流程如下：

基于动态规划的基本思想，先创建一个二维数组。存储出发位置到表格中每一个位置的最短路径之和。动态规划的基本套路就是步步为营，如果能保证从出发点到每一个位置的路径和都是最小的，自然能求解出到目标地的最短路径和。

在表先填充一些显然易见的值，也称为。如出发点的最短路径是本身，如下图所示：

表中的第一行的值，只受左边值的影响，不存在多个选择，也容易找出来。其值为。

表中的第一列的值只受上边值的影响，也不存在多个选择，其值为。

其它位置的值，需要在上边和左边的值里选择最小值后再与原数组中同位置的值相加。如下图所示位置可以有 个选择，选择其中较小的值。

以此类推，可得到余下所有位置的值。如下图所示，红色数字表示最终的选择。

最后绘制出从出发点到目标地的最短路径之和。

4.2 编码实现

5. 总结

递归、动态规划是算法世界的两大剑客，两者互通款曲，解决同一个问题时，一个站在问题域的正方向，一个站在问题域的反方向。灵活运用且掌握这两大算法，是通向算法界的必修之路。