动态规划-最大子序列问题

动态规划问题之前看了很久没有理解，今天看到一个题突然明白了点，写下此篇记录思考过程。

之前没看懂啥是动态规划就是因为很多文章上来就说什么状态转移方程，什么暴力穷举剪枝什么的，没学过这个的完全看不懂好嘛！你们在说些啥？？

本篇文章就是要搞清楚以下几个问题：

什么是动态规划？
为什么要动态规划？
什么是状态？什么是状态转移方程？
为什么要状态转移？
暴力穷举有什么问题？动态规划解决了什么问题？

动态规划的定义

最后看下动态规划的定义：

动态规划的英文名称为：dynamic programming，接下来看下《Introduction to algorithms》对动态规划的定义：

A dynamic-programming algorithm solves each subsubproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time it solves each subsubproblem.
动态规划算法解决每一个子问题，仅一次，然后保存子问题的结果到内存表中，以此来避免对子问题的重复计算。

题目是这样的：

最大子序列
题目描述
给出一个整数序列 S，其中有 N 个数，定义其中一个非空连续子序列 T 中所有数的和为 T 的“序列和”。
对于 S 的所有非空连续子序列 T，求最大的序列和。变量条件：N 为正整数，N≤1000000，结果序列和在范围（-2^63,2^63-1）以内。
输入描述:
第一行为一个正整数 N，第二行为 N 个整数，表示序列中的数。
输出描述:
输入可能包括多组数据，对于每一组输入数据，仅输出一个数，表示最大序列和。
示例 1
输入
5
1 5 -3 2 4
6
1 -2 3 4 -10 6
4
-3 -1 -2 -5
输出
9
7
-1

暴力循环，无状态影响

先说不考虑动态规划，直接无脑暴力循环的情况：

由于目标是输入序列的中间子串，头尾都不固定，因此至少两层循环：这样时间复杂度 $O (n^{2})$ ，输入序列越长耗时越长。因此在输入大于 $1 0^{4}$ 这个数量级时，很可能时间上就过不去了。

暴力循环解法相当于用时间换空间：因为中间过程都不保留，所以要把所有头尾中间子串全部遍历，只为求一个最大值。

存在的问题就是其实中间过程并不都有必要求一次，因为某段子串已经产生了负面影响（负数存在导致结果降低），包含这个子串的串都是无效答案，不可能得出最大值。

这就是【无状态影响】：即每次的结果不受之前结果影响，独立运算，因此会产生大量无效中间运算过程。

但本题中，“包含之前算过的子串的串无效”，这其实是有状态影响，我们可以根据之前的计算结果推算当前计算结果是否有效，【状态】指的就是上次计算结果对下次结果有没有影响。

前后状态有关联，因此产生了动态规划。

动态规划，有状态影响

先不说状态不状态的问题，单说这道题，暴力循环是将子序列当成头尾都在伸缩的串，那么动态规划是怎么思考的？

换个思路想，以某数为头、某数为尾限定的子串 -> 以某数结尾的子串。相当于掐住一头再看，这时二维的问题变成了一个一维的问题，所以这时问题复杂度降了一维，时间复杂度降为 $O (n)$ ，我们再来验证下这个想法是不是正确。

为什么可以这么想呢？

因为我们求的最大值不需要求中间结果，只需要知道【以某数为尾时子串能达到最大值】就够了。

而【状态影响】就是当上次我知道如果子串以-1 开头，就不用再往下算了，-1 开头的子串不可能得到所求的答案，上次的计算结果影响到了以后求解的策略。

这个状态影响如果用公式表达过来就是所谓的【状态转移方程】，本题的状态转移方程就是： $d p [i] = ma x (d p [i - 1] + n u m [i], n u m [i])$

翻译成人话来说就是：这次的结果等于，如果加上这个数比上次结果大就把和当成这次的结果；如果加上上次的结果还不如不加，那就干脆抛弃前面的结果，直接用加数作为这次的结果。（不管过程有啥，只要结果最大就行。）

动态规划本质是空间换时间，用 dp 数组保存每次计算的中间结果，然后根据前面的结果计算后面的，这样运行一遍之后 dp 数组中包含了所有状态（计算和）。

本题通过的代码：

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int N = sc.nextInt();
            int[] arr = new int [N];
            for (int i = 0; i < N; i++) {
                arr[i] = sc.nextInt();
            }// end input

            int[] dp = new int [N];
            dp[0] = arr[0];
            for (int i = 1; i < dp.length; i++) {
                dp[i] = arr[i]>(dp[i-1]+arr[i])?arr[i]:(dp[i-1]+arr[i]);
            }
            Arrays.sort(dp); // 求下dp的最大值
            System.out.println(dp[N-1]);
        }
    }
}

类似问题

类似经典问题：爬楼梯、背包问题等

爬楼梯

01 背包问题