# 动态规划

# 动态规划原理

基本思想： 问题的最优解如果可以由子问题的最优解推导得到，则可以先求解子问题的最优解，在构造原问题的最优解；若子问题有较多的重复出现，则可以自底向上从最终子问题向原问题逐步求解。

使用条件： 可分为多个相关子问题，子问题的解被重复使用

• Optimal substructure（优化子结构）：
  • 一个问题的优化解包含了子问题的优化解
  • 缩小子问题集合，只需那些优化问题中包含的子问题，降低实现复杂性
  • 我们可以自下而上的
• Subteties（重叠子问题）：在问题的求解过程中，很多子问题的解将被多次使用。

动态规划算法的设计步骤：

• 分析优化解的结构
• 递归地定义最优解的代价
• 自底向上地计算优化解的代价保存之，并获取构造最优解的信息
• 根据构造最优解的信息构造优化解 动态规划特点：
• 把原始问题划分成一系列子问题；
• 求解每个子问题仅一次，并将其结果保存在一个表中，以后用到时直接存取，不重复计算，节省计算时间
• 自底向上地计算。
• 整体问题最优解取决于子问题的最优解（状态转移方程）（将子问题称为状态，最终状态的求解归结为其他状态的求解）

# 步骤

• 问题拆解，找到问题之间的具体联系
• 状态定义
• 递推方程推导
• 实现

# 前提

1. 最大问题能否划分为多个小问题

2. 能否使用动态规划，取决于该问题是否能用动态规划解决的是这些小问题会不会被被重复调用。

# 题型

# 1. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

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

进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解题思路：

• 动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
• 如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
• 如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
• 每次比较 sum 和 ans 的大小，将最大值置为 ans，遍历结束返回结果
• 时间复杂度：O(n)O(n)

var maxSubArray = function(nums) {
    //存储最优结果
    let result = nums[0]
    //存储对最后结果有帮助的结果（只要大于0就有帮助）
    let n = 0
    for(let i=0;i<nums.length;i++){
        if(n<0){
            n = nums[i]
        }else{
            n += nums[i]
        }
        //result = Math.max(result,n)
        if(result<n) result = n
    }
    return result
};