|
算法题目中，动态规划类问题一直以来都是一块硬骨头。在刷了30道动态规划题目之后，对这类问题的解法小有一些心得体会，故总结成此文。
动态规划类问题本质上是将一个大问题拆分为许多小问题，通过对小问题进行求解，大问题复用小问题的答案，以得到最终解。这听以来和递归的思想有点像，因此一部分问题也可以用递归的方式进行求解，而动态规划则是对递归解法的一种优化。
我整体上将动态规划类问题分为两大部分：字符串类型的动规、数组类型的动规。针对每一个部分，又总结出了2～3种思考方向以供参考。下面分别来介绍每一部分
字符串类型的动规
遇到字符串类型的动态规划问题，我一般会从这三个方面考虑：
- 能否构造
dp数组来解决 - 能否利用回溯的方式来解决
- 其他方式（经验、规律等）
构造dp数组
首先来看如何构造dp数组来解决字符串类型的动态规划问题。在这类题目中，有一个常见但不成文的规律
- 如果问题涉及两个字符串
s1和s2，一般的解题思路为构造一个二维的dp[m+1][n+1]数组，其中m和n分别为字符串s1和s2的长度。数组中每一项dp[i][j]表示的含义是：s1的前i个字符和s2的前j个字符对于该问题的解，即当前问题的一个子问题的解。 - 如果问题涉及一个字符串
s1，一般的解题思路为构造一个一维的dp[m+1]数组，其中m为字符串s1的长度。一般来说，dp[i]的含义为字符串s1[0:i]对于该问题的解，即当前问题的一个子问题的解。
上述两个规律并不是绝对的，在大多数的题目中可以以此为切入点来寻找问题的解决方案。利用该解法的题目有如下：
- leetcode [10] 正则表达式匹配
- leetcode [32] 最长有效括号
- leetcode [97] 交错字符串
- leetcode [132] 分割回文串||
- leetcode [44] 通配符匹配
- leetcode [72] 编辑距离
- leetcode [91] 解码方法
- leetcode [115] 不同的子序列
回溯
如果构造dp数组依旧无法解决问题，可以尝试能否借助回溯的思想来解决问题。有如下问题应用到了回溯的思想：
- leetcode [87] 扰乱字符串
- leetcode [131] 分割回文串
- leetcode [22] 括号生成
其他方式
上述两种方式是基于字符串的动态规划问题的常见解题思路，也有部分问题的求解并不基于上述两种方式，而是根据其具体的特性、规律，有独特的求解方案。比如：
这是为数不多见的一道既没有利用dp数组求解、也没有利用回溯思路进行求解的题目，他主要利用了一个概念：回文中心。根据回文字符串的性质，可以发现其必有一个回文中心。比如：“aba"的回文中心是"b”；“abba"的回文中心是"bb”。那么一个回文串的回文中心可能有两种情况：回文中心为一个字符、或者回文中心为两个连续的字符。那么以遍历字符串，以每一/两个字符为回文中心，向两边进行扩展，来寻找最长的回文串。
数组类型的动规
数组类型的动态规划题目同样可以分为三部分，如下：
构造dp数组
构造dp数组，这是动规问题最基本的求解思路。和上述基于字符串类型的动规问题一样，基于数组类型的动规问题同样可以根据题目来决定：是要构造一维的dp数组、还是二维的dp数组？
不过基于数组的动规还是要比基于字符串的动规简单一些的，有以下题目可以用来练手
- leetcode [55] 跳跃游戏
- leetcode [62] 不同路径
- leetcode [45] 跳跃游戏||
- leetcode [53] 最大子数组和
- leetcode [63] 不同路径||
- leetcode [64] 最小路径和
- leetcode [70] 爬楼梯
- leetcode [120] 三角形最小路径和
- leetcode [300] 最长递增子序列
直观上的状态转移
有些题目可以直接直观的由题目得出有哪几种状态转移方式，这类题目的状态一般是有限个的、且相互之间可以进行转化。典型例题则是 leetcode 中的股票买卖问题
- leetcode [121] 买卖股票的最佳时机
- leetcode [122] 买卖股票的最佳时机||
- leetcode [123] 买卖股票的最佳时机|||
找规律
这部分题目就不多说了，多练多看吧，下面给出两道题目供参考
- leetcode [42] 接雨水
- leetcode [85] 最大矩形
上述总结了动态规划类问题中常见的一些题型、以及对应的解题思路。总的来说，拿到一道题目后，我们可以按照下面的步骤进行分析、尝试：
- 该问题能否拆分为小问题，是否可以构造
dp数组来解决，dp数组中的每一个元素的含义是什么（很重要，不同的定义方式直接影响解决问题的难易程度，甚至有的定义方式根本无法解决问题） - 定义完
dp数组后，画图分析，这是得到状态转移方程很重要的一步！有的状态转移不是很直观，但是我们可以通过画图分析，找到规律。
|