在文章[LeetCode]动态规划及LeetCode题解分析中，Jungle介绍到求解动态规划类问题，一般分为三个步骤，这里做个简单回顾：
动态规划是利用子问题的解推导出原问题的解，即用之前问题的解推导出之后问题的解，即利用已有的解（历史保存的解）来解未知的问题。我们一般使用数组（有一维的，更常用的是二维数组）来保存已有的解（历史记录）。
动态规划解题包括三大步骤：
（1）明确数组元素代表的含义
针对具体问题，声明了一个数组，那么这个数组每个元素代表什么含义？假设使用一维数组dp，每一项dp[i]代表什么意思？如果使用二维数组dp，每一项dp[i][j]代表什么含义？这是首先需要明确的。
（2）寻找递推关系（动态规划的关键），务必考虑特殊情况下的递推关系
以一维数组为例，明确了dp[i]的含义了，那么dp[i]和dp[i 1]是什么关系？可以通过怎样的关系式将二者关联起来？找到了这个递推关系，就可以知道任意i的时候的值。特殊情况是指比如存在边界条件，或者题目要求的某个范围，或者题目有特殊说明等。
（3）数组初始化
还是以一维数组为例，每一项dp[i]的含义明确了，dp[i]与dp[i 1]的关系式也找到了，总得有个最初的值吧，即dp[0]，有的时候由于0,1的特殊性，初始值甚至包括dp[1]，dp[2]等。
本文Jungle将应用上述总结的三个步骤，完成LeetCode上难度为【简单】的题目。
1
53.最大字序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
本题使用一维数组dp
（1）明确数组含义
dp[i]——保存到nums[i]时最大和的连续子数组的和。
（2）寻找递推关系
试想，如果到nums[i-1]时最大和为temp_sum，如何权衡要不要把nums[i]加入到当前的最大和里面呢？
- 如果temp_sum nums[i]比nums[i]都更小，那最大和还不如从nums[i]开始计算！
- 如果temp_sum nums[i]比nums[i]更大，那么可以把nums[i]加入到当前连续子数组序列。
所以递推关系可以推导如下：
- 如果dp[i-1]<temp_sum，那么dp[i] = temp_sum;
- 如果dp[i-1]>temp_sum，那么dp[i] = dp[i-1];
（3）数组初始化
显然，dp[0] = nums[0]
（4）Code
代码语言：javascript复制int maxSubArray(vector<int>& nums) {
int *dp = new int[nums.size()];
dp[0] = nums[0];
int temp = nums[0];
for (int i = 1; i<nums.size(); i ){
temp = temp nums[i] >nums[i] ? temp nums[i] : nums[i];
dp[i] = (dp[i - 1] >temp ? dp[i - 1] : temp);
}
return dp[nums.size() - 1];
}2
70.爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。 示例 1： 输入：2 输出：2 解释： 有两种方法可以爬到楼顶。 1. 1 阶 1 阶 2. 2 阶 示例 2：输入：3 输出：3 解释： 有三种方法可以爬到楼顶。
- 1 阶 1 阶 1 阶
- 1 阶 2 阶
- 2 阶 1 阶
本题使用一维数组dp（其实为节省空间可以不用数组，但为方便统一步骤，本解析仍用数组）
（1）明确数组含义
dp[i]——爬到第i个台阶时有多少种方法。
（2）寻找递推关系
爬到第i个台阶，既可以从第i-1个台阶爬一个台阶到达，也可以从第i-2个台阶爬2个台阶到达，所以递推关系为：
dp[i] = dp[i-1] dp[i-2]
（3）数组初始化
dp[1] = 1, dp[2] = 2
（4）Code
代码语言：javascript复制int climbStairs(int n) {
if (n <= 2){
return n;
}
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];
}3
买卖股票的最佳时机
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法计算你能获取的最大利润。注意你不能在买入股票前卖出股票。 示例 1: 输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。 示例 2: 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 最大利润为 0。
本题使用一维数组dp（其实本题可以直接利用传入的数组参数）
（1）明确数组含义
dp[i]——保存第i天交易时，以第i天之前的最低价格为准，获得的收益。
（2）寻找递推关系
其实该题目求的是在股价波峰与波谷之间的最大差，并且波峰在波谷后面出现。那么我们需要找到波谷（min）和之后出现的波峰（max）。所以对于第i天的股价prices[i]而言：
- 如果当天股价比之前出现的波谷（min）还小，那么肯定以当天的股价作为波谷（min），同时当天的收益dp[i]为0；
- 如果当天股价比波谷（min）大，那么当天的收益dp[i]为当天的股价与波谷股价之差；
那么最大的收益值即为数组dp里的最大值了。
（3）数组初始化
dp[0] = 0，min=prices[i]
（4）Code
代码语言：javascript复制int maxProfit(vector<int>& prices) {
int len = prices.size();
if (len == 0){
return 0;
}
int *dp = new int[len];
dp[0] = 0;
int min = prices[0];
int max = 0;
for (int i = 1; i<len; i ){
if (prices[i]<min){
min = prices[i];
dp[i] = 0;
}
else{
dp[i] = prices[i] - min;
if (dp[i]>max){
max = dp[i];
}
}
}
return max;
}4
198.打家劫舍
一个小偷，计划偷窃沿街的房屋。每间房内藏有一定的现金，影响你偷窃的唯一制约因素是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。 示例 1: 输入: [1,2,3,1]输出: 4 解释: 偷窃1号房屋 (1) ，然后偷窃3号房屋 (3)。偷窃到的最高金额=1 3=4 。 示例 2: 输入: [2,7,9,3,1]输出: 12 解释: 偷窃1号房屋 (2), 偷窃3号房屋 (9)，接着偷窃5号房屋 (1)。偷窃到最高金额=2 9 1=12 。
本题使用一维数组dp（其实本题可以直接利用传入的数组参数）
（1）明确数组含义
dp[i]——到第i号房屋为止，偷窃到的最高金额。
（2）寻找递推关系
到达第i号房屋时，如果第i-1已经偷盗了，显然第i号房屋不能再行窃；如果第i-1号房屋没有被偷盗，则比较偷盗第i号房屋后的最高金额与截止第i-1号房屋为止的最高金额dp[i-1]的大小：
dp[i] = max(dp[i-1], dp[i-2] nums[i])
（3）数组初始化
dp[0] = nums[0]
dp[1] = max(nums[0],nums[1])
（4）Code
代码语言：javascript复制int rob(vector<int>& nums) {
int len = nums.size();
if(len==0){
return 0;
}
if(len == 1){
return nums[0];
}
if(len == 2){
return nums[0]>nums[1]?nums[0]:nums[1];
}
int *dp = new int[nums.size()];
dp[0] = nums[0];
dp[1] = nums[1]>nums[0]?nums[1]:nums[0];
for(int i=2;i<nums.size();i ){
dp[i] = dp[i-2] nums[i]>dp[i-1]?dp[i-2] nums[i]:dp[i-1];
}
return dp[nums.size()-1];
}5
303.区域和检索
给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。 示例：给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange() sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3 说明: 你可以假设数组不可变。会多次调用 sumRange 方法。
本题使用一维数组dp
（1）明确数组含义
dp[i]——从nums[0]到nums[i]的和。
（2）寻找递推关系
显然：dp[i] = dp[i-1] nums[i]。
那么某个范围（i，j）之间的和？即nums[i] nums[i 1] ... nums[j]，也就是dp[j]-dp[i]
（3）数组初始化
dp[0] = nums[0]
dp[1] = max(nums[0],nums[1])
（4）Code
代码语言：javascript复制class NumArray {
public:
NumArray(vector<int>& nums) {
if(nums.size()==0){
return;
}
arrNum = new int[nums.size()];
arrNum[0] = nums[0];
for(int i=1;i<nums.size();i ){
arrNum[i] = arrNum[i-1] nums[i];
}
}
int sumRange(int i, int j) {
if(i==0){
return arrNum[j];
}
return arrNum[j]-arrNum[i-1];
}
int* arrNum;
};6
746.使用最小花费爬楼梯
数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。注意：cost 的长度将会在 [2, 1000]。每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。
示例 1: 输入: cost = [10, 15, 20] 输出: 15 解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。 示例 2: 输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 输出: 6 解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。
本题使用一维数组dp
（1）明确数组含义
dp[i]——经过第i级阶梯时，使用的最小花费的和。
（2）寻找递推关系
到达第i级阶梯时，要不要踏上第i级阶梯呢？这取决于在第i-2级阶梯时的最小花费值和第i-1级阶梯时的最小花费值，即：
dp[i] = 第i级阶梯所需的体力花费值 min(dp[i-2], dp[i-1])
（3）数组初始化
dp[0] = cost[0]，dp[1] = cost[1]
（4）Code
代码语言：javascript复制int minCostClimbingStairs(vector<int>& cost) {
if (cost.size() == 1){
return cost[0];
}
if (cost.size() == 2){
return cost[0]>cost[1] ? cost[1] : cost[0];
}
int *res = new int[cost.size()];
res[0] = cost[0];
res[1] = cost[1];
for (int i = 2; i<cost.size(); i ){
res[i] = cost[i] (res[i - 1]<res[i - 2] ? res[i - 1] : res[i - 2]);
}
return res[cost.size() - 1]<res[cost.size() - 2] ? res[cost.size() - 1] : res[cost.size() - 2];
}
