经典动态规划的问题来理解无后效性

Bertha 。 2023-10-11 17:04 13阅读 0赞

我们先看一下题目，从题目来进行切入

> 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。  
> 子数组 是数组中的一个连续部分。

示例：

> 输入：nums = \[-2,1,-3,4,-1,2,1,-5,4\]  
> 输出：6  
> 解释：连续子数组 \[4,-1,2,1\] 的和最大，为 6 。

题目链接：https://leetcode-cn.com/problems/maximum-subarray/  
这是一道非常经典的动态规划类题目，需要我们掌握动态规划问题设计状态的技巧（**无后效性**），并且需要知道如何推导状态转移方程，最后再去优化空间。  
什么叫无后效性？

## 无后效性 ##

为了保证计算子问题能够按照顺序、不重复地进行，动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做「无后效性」。  
换言之，动态规划对状态空间的遍历构成一张有向无环图，遍历就是该有向无环图的一个拓扑序。有向无环图中的节点对应问题中的「状态」，图中的边则对应状态之间的「转移」，转移的选取就是动态规划中的「决策」

## 设计状态思路 ##

> 把不确定的因素确定下来，进而把子问题定义清楚，把子问题定义得简单。动态规划的思想通过解决了一个一个简单的问题，进而把简单的问题的解组成了复杂的问题的解。

而本题可以看成以下几个子问题：

> 例如，示例 1 输入数组是 \[-2,1,-3,4,-1,2,1,-5,4\] ，我们可以求出以下子问题：  
> 子问题 1：经过 -2 的连续子数组的最大和是多少；  
> 子问题 2：经过 1 的连续子数组的最大和是多少；  
> 子问题 3：经过 −3 的连续子数组的最大和是多少；  
> 子问题 4：经过 4 的连续子数组的最大和是多少；  
> 子问题 5：经过 −1 的连续子数组的最大和是多少；  
> 子问题 6：经过 2 的连续子数组的最大和是多少；  
> 子问题 7：经过 1 的连续子数组的最大和是多少；  
> 子问题 8：经过 −5 的连续子数组的最大和是多少；  
> 子问题 9：经过 4 的连续子数组的最大和是多少。

一共九个子问题，但是每一个子问题均具有不确定性的地方（有后效性）,如:

> 经过 −3 的连续子数组  
> 对于数组\[-2,1,-3,4,-1,2,1,-5,4\]  
> 我们可以看出-3是\[-2,1,-3\]的第三个元素，是\[-1,-3\]的第二个元素,  
> 是\[-3,4,-1\]的第一个元素

那么我们需要将这些不确定性转化为确定，于是我们将本题再次划分为若干个子问题：

> 子问题 1：以 -2 **结尾**的连续子数组的最大和是多少；  
> 子问题 2：以 1 **结尾**的连续子数组的最大和是多少；  
> 子问题 3：以 −3 **结尾**的连续子数组的最大和是多少；  
> 子问题 4：以 4 **结尾**的连续子数组的最大和是多少；  
> 子问题 5：以 -1 **结尾**的连续子数组的最大和是多少；  
> 子问题 6：以 2 **结尾**的连续子数组的最大和是多少；  
> 子问题 7：以 1 **结尾**的连续子数组的最大和是多少；  
> 子问题 8：以 −5 **结尾**的连续子数组的最大和是多少；  
> 子问题 9：以 4 **结尾**的连续子数组的最大和是多少。

与之前划分的九个子问题相比，多了结尾两个字  
一旦我们加上结尾两个字，就将所有的不确定因素转化为了确定性因素

*  以 -2 **结尾**的连续子数组只有\[-2\]
 *  以 1 **结尾**的连续子数组是\[-2,1\]和\[1\]，此时我们只需要比较\[-2,1\]和\[1\]那个较大即可

## 定义状态（定义子问题） ##

我们以dp\[i\]表示以nums\[i\]为结尾的连续子数组的最大和  
接下来我们就可以定义**状态转移方程（描述子问题之间的联系）**  
根据状态的定义，由于 nums\[i\] 一定会被选取，并且以 nums\[i\] 结尾的连续子数组与以 nums\[i - 1\] 结尾的连续子数组只相差一个元素 nums\[i\]。  
假设数组 nums 的值全都严格大于 0，那么一定有 dp\[i\] = dp\[i - 1\] + nums\[i\]，于是就分为以下两种情况：

*  如果 dp\[i - 1\] > 0，那么可以把 nums\[i\] 直接接在 dp\[i - 1\] 表示的那个数组的后面，得到和更大的连续子数组；
 *  如果 dp\[i - 1\] <= 0，那么 nums\[i\] 加上前面的数 dp\[i - 1\] 以后值不会变大。于是 dp\[i\] 「另起炉灶」，此时单独的一个 nums\[i\] 的值，就是 dp\[i\]。

于是我们的状态转移方程就变为：

> dp\[i\]=max\{nums\[i\],dp\[i-1\]+nums\[i\]\}

## 初始值 ##

dp\[0\] 根据定义，只有 1 个数，一定以 nums\[0\] 结尾，因此 dp\[0\] = nums\[0\]。

## 输出值 ##

把所有的 dp\[0\]、dp\[1\]、……、dp\[n - 1\] 都走一遍，取最大值  
按照这种思路，我们开始编写代码：

public class Solution {
        
    
        public int maxSubArray(int[] nums) {
        
            int len = nums.length;
            // dp[i] 表示：以 nums[i] 结尾的连续子数组的最大和
            int[] dp = new int[len];
            dp[0] = nums[0];
    
            for (int i = 1; i < len; i++) {
        
                if (dp[i - 1] > 0) {
        
                    dp[i] = dp[i - 1] + nums[i];
                } else {
        
                    dp[i] = nums[i];
                }
            }
    
            // 也可以在上面遍历的同时求出 res 的最大值，这里我们为了语义清晰分开写，大家可以自行选择
            int res = dp[0];
            for (int i = 1; i < len; i++) {
        
                res = Math.max(res, dp[i]);
            }
            return res;
        }
    }