类似之处

都可以将问题拆解为子问题，通过解决子问题来解决原问题

动态规划 (Dynamic Programming)

DP = rescursion + re-use

递归解决子问题，为了不重复解决子问题，暂存已解决过的子问题

分而治之 (Divide and Conquer)

将问题拆分，并分别解决（分开治理），解决后合并子问题，得到原问题答案

贪心算法

求局部最优解，最终解决全局最优解

贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法

贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

总结

动态规划：各子问题重叠
分治：各子问题独立
贪心算法：对每个子问题都做出了选择，不能回退
动态规划：保存以前运算结果，并根据以前的运算结果做出选择，可以回退

例子学习法

最大子序和（子序：按顺序的子数组）

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

子数组是数组中的一个连续部分。示例 1：

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

示例 2：
输入：nums = [1]
输出：1

示例 3：
输入：nums = [5,4,-1,7,8]
输出：23

示例 4：
输入：nums = [-2]
输出：-2

提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104

作者：力扣 (LeetCode)

链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn3cg3/

来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

贪心

计算子数组以每一个元素结尾的最大和
如果之前和小于0，则抛弃
计算的过程中，将结果保存到原数组中，计算后，数组中最大值则为所求

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) 
    // 贪心
    for(let i = 1; i < nums.length; i++) {
        if (nums[i - 1] > 0) {
            nums[i] += nums[i - 1]
        }
    }

    return Math.max(...nums)
}
//           [-2, 1, -3, 4, -1, 2, 1, -5, 4]
// 循环一遍   [-2, 1,  -2, 4, 3, 5, 6, 1, 5]
// 第一步：以 -2 结尾的最大和为 -2
// 第二步： 以 1 结尾的最大和为 1（因为以-2结尾的最大和为负数）
// 第三步：以 -3 结尾的最大和为 -2 (加上前面的1)
// ...

动态规划解法

nums 数组长度为 n

f(i), 0 \< i \< n-1 表示子数组是以第 i 个数结尾的，和是子数组当中最大的
求出以每一位数结尾的最大子序和，并暂存到一个数组 memoArray 中
- 即求 max{f(i-1) + nums[i], nums[i]}
  - 求子问题，f(i-1)
- 误区
  - nums[i] > 0, f(i) = f(i - 1) + nums[i]
  - nums[i] <= 0, f(i) = f(i - 1) ❌ 因为需要以 nums[i] 结尾，所以要么是包含 f(i) ，要么 nums[i] 独立一个子数组
数组 memoArray 中的最大值，就是最大子序和
- 为了不用再次遍历数组 memoArray ，可以在计算的过程中用变量 maxAns 记录最大值

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let memoArray = [nums[0]]// 开辟空间 O(n)
    let maxAns = memoArray[0];
    let temp;
    for(let i = 0; i < nums.length - 1; i++) {
        temp = Math.max(memoArray[i] + nums[i+1], nums[i+1])
        memoArray[i + 1] = temp
        maxAns = Math.max(temp, maxAns)
    }
    return maxAns
};

分析

循环遍历数组，时间复杂度：O(n)
开辟一个数组存储 f(i) 空间复杂度：O(n)

进阶、优化

由于利用只关系到 f(i-1) ，所以可以利用一个变量 pre 来保存 f(i-1) 的值，类似移动数组思想，将空间复杂度优化到 O(1)

// 动态规划优化
let pre = 0;
let maxAns = nums[0];// 注意，初始化最大值时 为第一个数；如果初始化为0，数组为一个负数时会处理不了该边界问题
nums.forEach(num => {
    pre = Math.max(pre + num, num)// 求 f(i)
    maxAns = Math.max(pre, maxAns)// 记录最大值 maxAns
})

return maxAns

分治解法

参考： Difference between Divide and Conquer Algo and Dynamic Programming