简介

动态规划是一种通过将原问题分解为相对简单的子问题的方式求解复杂问题的方法，而能用动态规划解决的问题，需要满足三个条件：最优子结构、无后效性和子问题重叠。

最优子结构

tip

具有最优子结构的问题也可能是适合用贪心的方法求解。

• 要注意要确保我们考察了最优解中用到的所有子问题。
• 证明问题最优解的第一步是做出一个选择；
  对于一个给定问题，在其可能的第一步选择中，假定你已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择；
  给定可获得的最优解的选择后，确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间；
• 证明作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。
  方法是反证法，考虑加入某个子问题的解不是其自身的最优解，那么就可以从原问题的解中用该子问题的最优解替换掉当前的非最优解，从而得到原问题的一个更优的解，从而与原问题最优解的假设矛盾。
• 要保持子问题空间尽量简单，只在必要时扩展。

最优子结构的不同体现在两个方面:

1. 原问题的最优解中涉及多少个子问题；
2. 确定最优解使用哪些子问题时，需要考察多少种选择。

子问题图中每个定点对应一个子问题，而需要考察的选择对应关联至子问题顶点的边。

无后效性

已经求解的子问题，不会再受到后续决策的影响。

子问题重叠

如果有大量的重叠子问题，我们可以用空间将这些子问题的解存储下来，避免重复求解相同的子问题，从而提升效率。空间换时间

基本思路

对于一个能用动态规划解决的问题，一般采用如下思路解决：

1. 将原问题划分为若干阶段，每个阶段对应若干个子问题，提取这些子问题的特征（称之为状态）；
2. 寻找每一个状态的可能决策，或者说是各状态间的相互转移方式（用数学的语言描述就是状态转移方程）。
3. 按顺序求解每一个阶段的问题。

题目与题解

53. 最大子数组和

难度：中等

标签：数组 动态规划 分治

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

题解

用f(i)代表以第i个数结尾的连续子数组的最大和，那么要求的答案就是：max{f(i)}, 0≤i≤n-1

那么需要考虑的就是nums[i]单独成为一段还是加入f(i-1)对应的那一段

从而 f(i) = max(nums[i], f(i)+nums[i])

为了节省空间，只需要使用一个变量preSum来存取前一个位置的最大和即可

c++

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int maxSum = nums[0];
        int preSum = nums[0];
        for (int i = 1; i < n; ++i) {
            preSum = max(nums[i], preSum + nums[i]);
            maxSum = max(maxSum, preSum);
        }
        return maxSum;
    }
};