在文章[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上难度为【简单】的题目。

53. 最大子序和

https://leetcode-cn.com/problems/maximum-subarray/

给定一个整数数组 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

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];
}

70. 爬楼梯

https://leetcode-cn.com/problems/climbing-stairs/

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2       输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3        输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  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

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];
}

121. 买卖股票的最佳时机

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

给定一个数组，它的第 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

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;
}

198. 打家劫舍

https://leetcode-cn.com/problems/house-robber/

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 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

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];
    }

303. 区域和检索 - 数组不可变

https://leetcode-cn.com/problems/range-sum-query-immutable/

给定一个整数数组  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

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;
};

746. 使用最小花费爬楼梯

https://leetcode-cn.com/problems/min-cost-climbing-stairs/

数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。

每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。

您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。

示例 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。

注意：

cost 的长度将会在 [2, 1000]。
每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。

本题使用一维数组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

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];
}

1025. 除数博弈

https://leetcode-cn.com/problems/divisor-game/

爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。

最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：

选出任一 x，满足 0 < x < N 且 N % x == 0 。
用 N - x 替换黑板上的数字 N 。
如果玩家无法执行这些操作，就会输掉游戏。

只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。

 

示例 1：

输入：2    输出：true
解释：爱丽丝选择 1，鲍勃无法进行操作。
示例 2：

输入：3    输出：false
解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。

这题可以用动态规划，但更是一道数学题……

bool divisorGame(int N) {
    return N%2==0;
}

欢迎关注知乎专栏：Jungle是一个用Qt的工业Robot

欢迎关注Jungle的微信公众号：Jungle笔记

最后

以上就是多情长颈鹿为你收集整理的[LeetCode]动态规划LeetCode[简单]题全解53. 最大子序和70. 爬楼梯121. 买卖股票的最佳时机198. 打家劫舍303. 区域和检索 - 数组不可变746. 使用最小花费爬楼梯1025. 除数博弈的全部内容，希望文章能够帮你解决[LeetCode]动态规划LeetCode[简单]题全解53. 最大子序和70. 爬楼梯121. 买卖股票的最佳时机198. 打家劫舍303. 区域和检索 - 数组不可变746. 使用最小花费爬楼梯1025. 除数博弈所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。