什么是动态规划？

给定一个复杂问题，将其拆分为多个简单子问题。根据子问题答案反推出复杂问题的答案

核心思想

  • 拆分子问题

  • 求解子问题

  • 记录子问题答案

  • 反推父问题答案

动态规划算法即通过记住子问题的答案来节约时间

解题思路

以一道LeetCode的题目为例：

1
2
3
4
5
6
7
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

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

大致思路

动态规划有几个典型特征，最优子结构、状态转移方程、边界、重叠子问题。

我们求解动态规划问题的大致思路为:

  • 枚举分析

  • 确定边界值

  • 找出规律，得到最优子结构

  • 写出状态转移方程

具体过程

观察规律，采用自底向上方法枚举分析:

  1. -2 最大子数组 [-2]

  2. 1 最大子数组 [1]

  3. -3 最大子数组 [1]

  4. 4 最大子数组 [4]

  5. -1 最大子数组 [4]

  6. 2 最大子数组 [4, -1, 2]

  7. 1 最大子数组 [4, -1, 2, 1]

  8. -5 最大子数组 [4, -1, 2, 1]

  9. 4 最大子数组 [4, -1, 2, 1]

我们以f(n)来表示以第n个元素结尾的连续子数组的最大和，则maxSubArray = max(f(1), f(2),…,f(n))

因此我们只需要找出f(n)和f(n-1)之间的关系即可写出动态规划的状态转移方程

观察枚举结果我们发现:

f(n)要么是nums[n]的值，要么是nums[n]与第n-1个元素结尾的连续子数组的最大和之和

即状态转移方程为: f(n) = max(f(n-1) + nums[n], nums[n])

而边界值显而易见的为nums[0]

至此我们就可以写出该题的动态规划解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSubArray = nums[0];
        int preArray = 0;
        for (const auto &x: nums)
        {
            preArray = max(preArray + x, x);
            maxSubArray = max(maxSubArray, preArray);
        }
        return maxSubArray;
    }
};