动态规划
动态规划（英语：Dynamic programming，简称 DP），是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。
用动态规划解决问题的关键是写出状态转移方程，也就是如何使用子问题的结果推导出大问题的结果的方程。举一个最简单的例子：求一个数组\(a_i\)中最大的数。如果知道前\(n\)项的最大数是\(max_n\)，那么前\(n+1\)项的最大数就是：
（当然二分法会更快，这里只是举一个例子）。以高中的知识范畴，有一点数列递推公式的感觉。
例子
LeetCode 53：给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。
如果我们已经知道包含第n项的前n项的具有最大和为\(sum_n\)，那么\(\(sum_{n+1} = max(a_{n+1}, sum_n+a_{n+1})\)\)，题目的解就是\(MAX_n^N(sum_n)\)。
LeetCode 152：给你一个整数数组 nums ，请你找出一个具有最大乘积的连续子数组（子数组最少包含一个元素），返回其最大乘积。
乍一看和上面一模一样。不过乘法要考虑负数。所以如果我们已经知道包含第n项的前n项的具有最大乘积为\(maxp_n\)，最小乘积为\(minp_n\)，那么状态转移方程为：\(\(maxp_{n+1} = max(a_{n+1}, maxp_n\times a_{n+1}, minp_n\times a_{n+1})\)\)，\(\(minp_{n+1} = min(a_{n+1}, maxp_n\times a_{n+1}, minp_n\times a_{n+1})\)\)，题目的解就是\(MAX_n^N(maxp_n)\)。
LeetCode 279：给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。例如，n=13，最少是2个完全平方数9+4的和。
设和为 \(x\) 的完全平方数的最少数量为\(f(x)\)，我们有\(f(x) = MIN_{a=1}^x{ f(n-a)+f(a)}\)。并且如果\(x\)是完全平方数有\(f(x) = 1\)。
还有更好的状态转移方程。考虑到我们必须要选完全平方数，\(\(f(x) = MIN_{a=1}^{\lfloor \sqrt n \rfloor} f(a^2)+f(n-a^2)\)\)