\qquad
一、什么是动态规划动态规划将一个大问题，按照同一个模型（通过数学建模得出的一个推导公式），逐层往下拆解，直到找到基准状态（一个已知的答案或者一个容易被求解的问题）；然后再根据得出的推导公式自底向上逐层求解（期间保存每一层得出的答案），从而最终得出大问题的答案。 可以用12个字概括： 自顶向下拆解，自底向上求解
注意： 动态规划和分而治之都采用了分治思想，不同的是： 分而治之拆分出来的子问题是离散的，相互之间没有关系； 而 动态规划拆解出来的子问题是具有层级关系的父子问题。 父问题答案=子问题答案+差异部分的答案
\qquad
二、思考动态规划问题的四个步骤一般解决动态规划问题，分为四个步骤，分别是
问题拆解，找到问题之间的具体联系状态定义递推方程推导实现下面通过一个简单的例子来讲解：
“1+1+1+1+1+1+1+1” 得出答案是 8，那么如何快速计算 “1+ 1+1+1+1+1+1+1+1”？ \qquad
1、问题拆解，找到问题之间的具体联系 我们首先可以对这个大的问题进行拆解，这里我说的大问题是 9 个 1 相加，这个问题可以拆解成 1 + “8 个 1 相加的答案”，8 个 1 相加继续拆，可以拆解成 1 + “7 个 1 相加的答案”，… 1 + “0 个 1 相加的答案”，到这里， 第一个步骤 已经完成。\qquad
2、状态定义 状态定义 其实是需要思考在解决一个问题的时候我们做了什么事情，然后得出了什么样的答案，对于这个问题，当前问题的答案就是当前的状态，基于上面的问题拆解，你可以发现两个相邻的问题的联系其实是 后一个问题的答案 = 前一个问题的答案 + 1 ，这里，状态的每次变化就是 +1。\qquad
3、递推方程推导 定义好了状态，递推方程就变得非常简单，就是 dp[i] = dp[i - 1] + 1 ，这里的 dp[i] 记录的是当前问题的答案，也就是当前的状态， dp[i - 1] 记录的是之前相邻的问题的答案，也就是之前的状态，它们之间通过 +1 来实现状态的变更。\qquad
4、实现 最后一步就是实现了，有了状态表示和递推方程，实现这一步上需要重点考虑的其实是初始化，就是用什么样的数据结构，根据问题的要求需要做那些初始值的设定。 public int dpExample(int n) { int[] dp = new int[n + 1]; // 多开一位用来存放 0 个 1 相加的结果 dp[0] = 0; // 0 个 1 相加等于 0 for (int i = 1; i <= n; ++i) { dp[i] = dp[i - 1] + 1; } return dp[n]; }\qquad
PS：动态规划这四个步骤其实是相互递进的，状态的定义离不开问题的拆解，递推方程的推导离不开状态的定义，最后的实现代码的核心其实就是递推方程，这中间如果有一个步骤卡壳了则会导致问题无法解决，当问题的复杂程度增加的时候，这里面的思维复杂程度会上升。
\qquad 接下来我们再来看看 LeetCode 上面的几道题目，通过题目再来走一下这些个分析步骤。
\qquad
三、题目实战但凡涉及到动态规划的题目都离不开一道例题：爬楼梯（LeetCode 第 70 号问题）。
\qquad
题目一：爬楼梯假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入：2 输出：2 解释： 有两种方法可以爬到楼顶。
1 阶 + 1 阶2 阶示例 2：
输入：3 输出：3 解释： 有三种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶1 阶 + 2 阶2 阶 + 1 阶 题目解析爬楼梯，可以爬一步也可以爬两步，问有多少种不同的方式到达终点，我们按照上面提到的四个步骤进行分析：
问题拆解 \qquad 我们到达第 n 个楼梯可以从第 n - 1 个楼梯和第 n - 2 个楼梯到达，因此第 n 个问题可以拆解成第 n - 1 个问题和第 n - 2 个问题，第 n - 1 个问题和第 n - 2 个问题又可以继续往下拆，直到第 0 个问题，也就是第 0 个楼梯 (起点)\qquad
状态定义 \qquad “问题拆解” 中已经提到了，第 n 个楼梯会和第 n - 1 和第 n - 2 个楼梯有关联，那么具体的联系是什么呢？你可以这样思考，第 n - 1 个问题里面的答案其实是从起点到达第 n - 1 个楼梯的路径总数，n - 2 同理，从第 n - 1 个楼梯可以到达第 n 个楼梯，从第 n - 2 也可以，并且路径没有重复，因此我们可以把第 i 个状态定义为 “从起点到达第 i 个楼梯的路径总数”，状态之间的联系其实是相加的关系。 \qquad \qquad 递推方程 \qquad “状态定义” 中我们已经定义好了状态，也知道第 i 个状态可以由第 i - 1 个状态和第 i - 2 个状态通过相加得到，因此递推方程就出来了 dp[i] = dp[i - 1] + dp[i - 2]\qquad
实现 \qquad 你其实可以从递推方程看到，我们需要有一个初始值来方便我们计算，起始位置不需要移动 dp[0] = 0，第 1 层楼梯只能从起始位置到达，因此 dp[1] = 1，第 2 层楼梯可以从起始位置和第 1 层楼梯到达，因此 dp[2] = 2，有了这些初始值，后面就可以通过这几个初始值进行递推得到。\qquad
参考代码 public int climbStairs(int n) { if (n == 1) { return 1; } int[] dp = new int[n + 1]; // 多开一位，考虑起始位置 dp[0] = 0; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; ++i) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; }\qquad
题目二：最大子序和LeetCode 第 53 号问题：最大子序和。
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 \qquad 示例: \qquad 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 \qquad 进阶: \qquad 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
\qquad
题目解析求最大子数组和，非常经典的一道题目，这道题目有很多种不同的做法，而且很多算法思想都可以在这道题目上面体现出来，比如动态规划、贪心、分治，还有一些技巧性的东西，比如前缀和数组，这里还是使用动态规划的思想来解题，套路还是之前的四步骤：
问题拆解 \qquad 问题的核心是子数组，子数组可以看作是一段区间，因此可以由起始点和终止点确定一个子数组，两个点中，我们先确定一个点，然后去找另一个点，比如说，如果我们确定一个子数组的截止元素在 i 这个位置，这个时候我们需要思考的问题是 “以 i 结尾的所有子数组中，和最大的是多少？”，然后我们去试着拆解，这里其实只有两种情况：
i 这个位置的元素自成一个子数组;
i 位置的元素的值 + 以 i - 1 结尾的所有子数组中的子数组和最大的值 \qquad 你可以看到，我们把第 i 个问题拆成了第 i - 1 个问题，之间的联系也变得清晰 \qquad \qquad
状态定义 \qquad 通过上面的分析，其实状态已经有了，dp[i] 就是 “以 i 结尾的所有子数组的最大值”
\qquad
递推方程 \qquad 拆解问题的时候也提到了，有两种情况，即当前元素自成一个子数组，另外可以考虑前一个状态的答案，于是就有了 dp[i] = Math.max(dp[i - 1] + array[i], array[i]) \qquad 化简一下就成了： dp[i] = Math.max(dp[i - 1], 0) + array[i]\qquad
实现 \qquad 题目要求子数组不能为空，因此一开始需要初始化，也就是 dp[0] = array[0]，保证最后答案的可靠性，另外我们需要用一个变量记录最后的答案，因为子数组有可能以数组中任意一个元素结尾\qquad
参考代码 public int maxSubArray(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int n = nums.length; int[] dp = new int[n]; dp[0] = nums[0]; int result = dp[0]; for (int i = 1; i < n; ++i) { dp[i] = Math.max(dp[i - 1], 0) + nums[i]; result = Math.max(result, dp[i]); } return result; }对代码进行优化：
public int maxSubArray(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int thisSum = nums[0]; int result = thisSum ; for (int i = 1; i < nums.length; ++i) { thisSum = Math.max(thisSum , 0) + nums[i]; result = Math.max(result, thisSum ); } return result; }\qquad
总 结通过这几个简单的例子，相信你不难发现，解动态规划题目其实就是拆解问题，定义状态的过程，严格说来，动态规划并不是一个具体的算法，而是凌驾于算法之上的一种 思想。 \qquad
这种思想强调的是从局部最优解通过一定的策略推得全局最优解，从子问题的答案一步步推出整个问题的答案，并且利用空间换取时间。从很多算法之中你都可以看到动态规划的影子，所以，还是那句话 技术都是相通的，找到背后的本质思想是关键。
