动态规划LeetCode[简单]题全解

在文章[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

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

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

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

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

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

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