什么样的问题应该使用动态规划
说起动态规划，我不知道你有没有这样的困扰，在掌握了一些基础算法和数据结构之后，碰到一些较为复杂的问题还是无从下手，面试时自然也是胆战心惊。如果我说动态规划是个玄幻的问题其实也不为过。究其原因，我觉得可以归因于这样两点：
你对动态规划相关问题的套路和思想还没有完全掌握；
你没有系统地总结过究竟有哪些问题可以用动态规划解决。
知己知彼，你想把动态规划作为你的面试武器之一，就得足够了解它；而应对面试，总结、归类问题其实是个不错的选择，这在我们刷题的时候其实也能感觉得到。那么，我们就针对以上两点，系统地谈一谈究竟什么样的问题可以用动态规划来解。
一、动态规划是一种思想
动态规划算法，这种叫法我想你应该经常听说。嗯，从道理上讲这么叫我觉得也没错，首先动态规划它不是数据结构，这一点毋庸置疑，并且严格意义上来说它就是一种算法。但更加准确或者更加贴切的提法应该是说动态规划是一种思想。那算法和思想又有什么区别呢？
一般来说，我们都会把算法和数据结构放一起来讲，这是因为它们之间密切相关，而算法也往往是在特定数据结构的基础之上对解题方案的一种严谨的总结。
比如说，在一个乱序数组的基础上进行排序，这里的数据结构指的是什么呢？很显然是数组，而算法则是所谓的排序。至于排序算法，你可以考虑使用简单的冒泡排序或效率更高的快速排序方法等等来解决问题。
没错，你应该也感觉到了，算法是一种简单的经验总结和套路。那什么是思想呢？相较于算法，思想更多的是指导你我来解决问题。
比如说，在解决一个复杂问题的时候，我们可以先将问题简化，先解决简单的问题，再解决难的问题，那么这就是一种指导解决问题的思想。另外，我们常说的分治也是一种简单的思想，当然它在诸如归并排序或递归算法当中会常常被提及。
而动态规划就是这样一个指导我们解决问题的思想：你需要利用已经计算好的结果来推导你的计算，即大规模问题的结果是由小规模问题的结果运算得来的。
总结一下：算法是一种经验总结，而思想则是用来指导我们解决问题的。既然动态规划是一种思想，那它实际上就是一个比较抽象的概念了，也很难和实际的问题关联起来。所以说，弄清楚什么样的问题可以使用动态规划来解就显得十分重要了。
二、动态规划问题的特点
动态规划作为运筹学上的一种最优化解题方法，在算法问题上已经得到广泛应用。接下来我们就来看一下动归问题所具备的一些特点。
2.1 最优解问题
除非你碰到的问题是简单到找出一个数组中最大的值这样，对这种问题来说，你可以对数组进行排序，然后取数组头或尾部的元素，如果觉得麻烦，你也可以直接遍历得到最值。不然的话，你就得考虑使用动态规划来解决这个问题了。这样的问题一般都会让你求最大子数组、求最长递增子数组、求最长递增子序列或求最长公共子串、子序列等等。
如果碰到求最值问题，我们可以使用下面的套路来解决问题：
优先考虑使用贪心算法的可能性；
然后是暴力递归进行穷举，针对数据规模不大的情况；
如果上面两种都不适合，那么再选择动态规划。
可以看到，求解动态规划的核心问题其实就是穷举。当然了，动态规划问题也不会这么简单了事，我们还需要考虑待解决的问题是否存在重叠子问题、最优子结构等特性。
清楚了动态规划算法的特点，接下来我们就来看一下哪些问题适合用动态规划思想来解题。
1. 乘积最大子数组
给你一个整数数组 numbers，找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），返回该子数组的乘积。
示例1：
输入: [2,7,-2,4]
输出: 14
解释: 子数组 [2,7] 有最大乘积 14。
示例2：
输入: [-5,0,3,-1]
输出: 3
解释: 结果不能为 15, 因为 [-5,3,-1] 不是子数组，是子序列。
首先，很明显这个题目当中包含一个“最”字，使用动态规划求解的概率就很大。这个问题的目的就是从数组中寻找一个最大的连续区间，确保这个区间的乘积最大。由于每个连续区间可以划分成两个更小的连续区间，而且大的连续区间的结果是两个小连续区间的乘积，因此这个问题还是求解满足条件的最大值，同样可以进行问题分解，而且属于求最值问题。同时，这个问题与求最大连续子序列和比较相似，唯一的区别就是你需要在这个问题里考虑正负号的问题，其它就相同了。
对应实现代码：
class Solution {
public:
int maxProduct(vector<int>& nums) {
if(nums.empty()) return 0;
int curMax = nums[0];
int curMin = nums[0];
int maxPro = nums[0];
for(int i=1; i<nums.size(); i++){
int temp = curMax; // 因为curMax在下一行可能会被更新，所以保存下来
curMax = max(max(curMax*nums[i], nums[i]), curMin*nums[i]);
curMin = min(min(curMin*nums[i], nums[i]), temp*nums[i]);
maxPro = max(curMax, maxPro);
}
return maxPro;
}
};
2. 最长回文子串
问题：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例1：
输入: "babad"
输出: "bab"
示例2：
输入: "cbbd"
输出: "bb"
【回文串】是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。这个问题依然包含一个“最”字，同样由于求解的最长回文子串肯定包含一个更短的回文子串，因此我们依然可以使用动态规划来求解这个问题。
对应实现代码：
class Solution {
public boolean isPalindrome(String s, int b, int e){//判断s[b...e]是否为回文字符串
int i = b, j = e;
while(i <= j){
if(s.charAt(i) != s.charAt(j)) return false;
++i;
--j;
}
return true;
}
public String longestPalindrome(String s) {
if(s.length() <=1){
return s;
}
int l = 1, j = 0, ll = 1;
for(int i = 1; i < s.length(); ++i){
//下面这个if语句就是用来维持循环不变式，即ll恒表示：以第i个字符为尾的最长回文子串的长度
if(i - 1 - ll >= 0 && s.charAt(i) == s.charAt(i-1-ll)) ll += 2;
else{
while(true){//重新确定以i为边界，最长的回文字串长度。确认范围为从ll+1到1
if(ll == 0||isPalindrome(s,i-ll,i)){
++ll;
break;
}
--ll;
}
}
if(ll > l){//更新最长回文子串信息
l = ll;
j = i;
}
}
return s.substring(j-l+1, j+1);//返回从j-l+1到j长度为l的子串
}
}
3. 最长上升子序列
问题：给定一个无序的整数数组，找到其中最长上升子序列的长度。可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
示例：
输入: [10,9,2,5,3,7,66,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,66]，它的长度是 4。这个问题依然是一个最优解问题，假设我们要求一个长度为 5 的字符串中的上升自序列，我们只需要知道长度为 4 的字符串最长上升子序列是多长，就可以根据剩下的数字确定最后的结果。
对应实现代码：
class Solution {
public int lengthOfLIS(int[] nums) {
if(nums.length == 0) return 0;
int[] dp = new int[nums.length];
int res = 0;
Arrays.fill(dp, 1);
for(int i = 0; i < nums.length; i++) {
for(int j = 0; j < i; j++) {
if(nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
}
res = Math.max(res, dp[i]);
}
return res;
}
}
2.2 求可行性
如果有这样一个问题，让你判断是否存在一条总和为 x 的路径（如果找到了，就是 True；如果找不到，自然就是 False），或者让你判断能否找到一条符合某种条件的路径，那么这类问题都可以归纳为求可行性问题，并且可以使用动态规划来解。
1. 凑零兑换问题
问题：给你 k 种面值的硬币，面值分别为 c1, c2 … ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。
示例1：
输入: c1=1, c2=2, c3=5, c4=7, amount = 15
输出: 3
解释: 11 = 7 + 7 + 1。
示例2：
输入: c1=3, amount =7
输出: -1
解释: 3怎么也凑不到7这个值。
这个问题显而易见，如果不可能凑出我们需要的金额（即 amount），最后算法需要返回 -1，否则输出可能的硬币数量。这是一个典型的求可行性的动态规划问题。
对于示例代码：
class Solution {
public int coinChange(int[] coins, int amount) {
if(coins.length == 0)
return -1;
//声明一个amount+1长度的数组dp，代表各个价值的钱包，第0个钱包可以容纳的总价值为0，其它全部初始化为无穷大
//dp[j]代表当钱包的总价值为j时，所需要的最少硬币的个数
int[] dp = new int[amount+1];
Arrays.fill(dp,1,dp.length,Integer.MAX_VALUE);
for (int coin : coins) {
for (int j = coin; j <= amount; j++) {
if(dp[j-coin] != Integer.MAX_VALUE) {
dp[j] = Math.min(dp[j], dp[j-coin]+1);
}
}
}
if(dp[amount] != Integer.MAX_VALUE)
return dp[amount];
return -1;
}
}2. 字符串交错组成问题
问题：给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
示例1：
输入: s1="aabcc",s2 ="dbbca",s3="aadbbcbcac"
输出: true
解释: 可以交错组成。
示例2：
输入: s1="aabcc",s2="dbbca",s3="aadbbbaccc"
输出: false
解释:无法交错组成。
这个问题稍微有点复杂，但是我们依然可以通过子问题的视角，首先求解 s1 中某个长度的子字符串是否由 s2 和 s3 的子字符串交错组成，直到求解整个 s1 的长度为止，也可以看成一个包含子问题的最值问题。
对应示例代码：
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int length = s3.length();
// 特殊情况处理
if(s1.isEmpty() && s2.isEmpty() && s3.isEmpty()) return true;
if(s1.isEmpty()) return s2.equals(s3);
if(s2.isEmpty()) return s1.equals(s3);
if(s1.length() + s2.length() != length) return false;
int[][] dp = new int[s2.length()+1][s1.length()+1];
// 边界赋值
for(int i = 1;i < s1.length()+1;i++){
if(s1.substring(0,i).equals(s3.substring(0,i))){
dp[0][i] = 1;
}
}
for(int i = 1;i < s2.length()+1;i++){
if(s2.substring(0,i).equals(s3.substring(0,i))){
dp[i][0] = 1;
}
}
for(int i = 2;i <= length;i++){
// 遍历 i 的所有组成（边界除外）
for(int j = 1;j < i;j++){
// 防止越界
if(s1.length() >= j && i-j <= s2.length()){
if(s1.charAt(j-1) == s3.charAt(i-1) && dp[i-j][j-1] == 1){
dp[i-j][j] = 1;
}
}
// 防止越界
if(s2.length() >= j && i-j <= s1.length()){
if(s2.charAt(j-1) == s3.charAt(i-1) && dp[j-1][i-j] == 1){
dp[j][i-j] = 1;
}
}
}
}
return dp[s2.length()][s1.length()]==1;
}
}
2.3 求总数
除了求最值与可行性之外，求方案总数也是比较常见的一类动态规划问题。比如说给定一个数据结构和限定条件，让你计算出一个方案的所有可能的路径，那么这种问题就属于求方案总数的问题。
1. 硬币组合问题
问题：英国的英镑硬币有 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), 和 £2 (200p)。比如我们可以用以下方式来组成 2 英镑：1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p。问题是一共有多少种方式可以组成 n 英镑? 注意不能有重复，比如 1 英镑 +2 个 50P 和 50P+50P+1 英镑是一样的。
示例1：
输入: 2
输出: 73682
这个问题本质还是求满足条件的组合，只不过这里不需要求出具体的值或者说组合，只需要计算出组合的数量即可。
public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
int coin[] = { 1, 5, 10, 20, 50, 100 };
// dp[i][j]表示用前i种硬币凑成j元的组合数
long[][] dp = new long[7][n + 1];
for (int i = 1; i <= n; i++) {
dp[0][i] = 0; // 用0种硬币凑成i元的组合数为0
}
for (int i = 0; i <= 6; i++) {
dp[i][0] = 1; // 用i种硬币凑成0元的组合数为1,所有硬币均为0个即可
}
for (int i = 1; i <= 6; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = 0;
for (int k = 0; k <= j / coin[i - 1]; k++) {
dp[i][j] += dp[i - 1][j - k * coin[i - 1]];
}
}
}
System.out.print(dp[6][n]);
}
sc.close();
}
}
2. 路径规划问题
问题：一个机器人位于一个 m x n 网格的左上角。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角，共有多少路径？
示例1：
输入: 2 2
输出: 2
示例1：
输入: 3 3
输出: 6
这个问题还是一个求满足条件的组合数量的问题，只不过这里的组合变成了路径的组合。我们可以先求出长宽更小的网格中的所有路径，然后再在一个更大的网格内求解更多的组合。这和硬币组合的问题相比没有什么本质区别。
这里有一个规律或者说现象需要强调，那就是求方案总数的动态规划问题一般都指的是求“一个”方案的所有具体形式。如果是求“所有”方案的具体形式，那这种肯定不是动态规划问题，而是使用传统递归来遍历出所有方案的具体形式。
为什么这么说呢？因为你需要把所有情况枚举出来，大多情况下根本就没有重叠子问题给你优化。即便有，你也只能使用备忘录对遍历进行一个简单加速。但本质上，这类问题不是动态规划问题。
对应示例代码：
package com.qst.Tesst;
import java.util.Scanner;
public class Test12 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int x = scanner.nextInt();
int y = scanner.nextInt();
//设置路径
long[][] path = new long[x + 1][y + 1];
//设置领导数量
int n = scanner.nextInt();
//领导位置
for (int i = 0; i < n; i++) {
int a = scanner.nextInt();
int b = scanner.nextInt();
path[a][b] = -1;
}
for (int i = 0; i <= x; i++) {
path[i][0] = 1;
}
for (int j = 0; j <= y; j++) {
path[0][j] = 1;
}
for (int i = 1; i <= x; i++) {
for (int j = 1; j <= y; j++) {
if (path[i][j] == -1) {
path[i][j] = 0;
} else {
path[i][j] = path[i - 1][j] + path[i][j - 1];
}
}
}
System.out.println(path[x][y]);
}
}
}
三、 如何确认动态规划问题
从前面我所说来看，如果你碰到了求最值、求可行性或者是求方案总数的问题的话，那么这个问题就八九不离十了，你基本可以确定它就需要使用动态规划来解。但是，也有一些个别情况需要注意：
3.1 数据不可排序
假设我们有一个无序数列，希望求出这个数列中最大的两个数字之和。很多初学者刚刚学完动态规划会走火入魔到看到最优化问题就想用动态规划来求解，事实上，这个问题不是简单做一个排序或者做一个遍历就可以求解出来的。对于这种问题，我们应该先考虑一下能不能通过排序来简化问题，如果不能，才极有可能是动态规划问题。
最小的 k 个数
问题：输入整数数组 arr ，找出其中最小的 k 个数。例如，输入 4、5、1、6、2、7、3、8 这 8 个数字，则最小的 4 个数字是 1、2、3、4。
示例1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例2：
输入：arr = [0,1,2,1], k = 1
输出：[0]
我们发现虽然这个问题也是求“最”值，但其实只要通过排序就能解决，所以我们应该用排序、堆等算法或者数据结构就可以解决，而不应该用动态规划。
对应的示例代码：
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
int t;
boolean flag;
ArrayList result = new ArrayList();
if(k>input.length){
return result;
}
for(int i =0;i<input.length;i++){
flag = true;
for(int j = 0; j < input.length-i;j++)
if(j<input.length-i-1){
if(input[j] > input[j+1]) {
t = input[j];
input[j] = input[j+1];
input[j+1] = t;
flag = false;
}
}
if(flag)break;
}
for(int i = 0; i < k;i++){
result.add(input[i]);
}
return result;
}
}
3.2 数据不可交换
还有一类问题，可以归类到我们总结的几类问题里去，但是不存在动态规划要求的重叠子问题（比如经典的八皇后问题），那么这类问题就无法通过动态规划求解。
全排列
问题：给定一个没有重复数字的序列，返回其所有可能的全排列。
示例：
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
这个问题虽然是求组合，但没有重叠子问题，更不存在最优化的要求，因此可以使用回溯方法处理。
对应的示例代码：
public class Main {
public static void main(String[] args) {
perm(new int[]{1,2,3},new Stack<>());
}
public static void perm(int[] array, Stack<Integer> stack) {
if(array.length <= 0) {
//进入了叶子节点，输出栈中内容
System.out.println(stack);
} else {
for (int i = 0; i < array.length; i++) {
//tmepArray是一个临时数组，用于就是Ri
//eg：1，2，3的全排列，先取出1，那么这时tempArray中就是2，3
int[] tempArray = new int[array.length-1];
System.arraycopy(array,0,tempArray,0,i);
System.arraycopy(array,i+1,tempArray,i,array.length-i-1);
stack.push(array[i]);
perm(tempArray,stack);
stack.pop();
}
}
}
}总结一下，哪些问题可以使用动态规划呢，通常含有下面情况的一般都可以使用动态规划来解决：
求最优解问题（最大值和最小值）；
求可行性（True 或 False）；
求方案总数；
数据结构不可排序（Unsortable）；
算法不可使用交换（Non-swappable）。
如果面试题目出现这些特征，那么在 90% 的情况下你都能断言它就是一个动归问题。除此之外，还需要考虑这个问题是否包含重叠子问题与最优子结构，在这个基础之上你就可以 99% 断言它是否为动归问题，并且也顺势找到了大致的解题思路。
作者：xiangzhihong
