力扣初级算法（六）【动态规划】

本文中的题目均来自力扣，代码默认以C#实现，伪代码仅用来帮助描述，不严格遵循某种语言的语法。

本章中是一些经典的动态规划面试问题。

我们推荐以下题目：爬楼梯，买卖股票最佳时机 和 最大子序和。

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 阶

解题思路

• 朴素的想法是，穷举所有的肯能，这在问题规模比较小的时候，是可行的，但当问题规模扩大的时候，我们似乎没有办法一次性列举所有的可能。
• 稍加思考，我们观察一些题目，看看一个较大规模的问题的答案能否根据一些较小规模的问题求得。
• 我们每次可以爬1个或者2个台阶，也就是说，在每一层台阶上，我都有两种选择。
• 但是当我即将到达楼顶的时候，比如说我现在第八个台阶上，楼顶在第九个台阶上，我只能选择爬一个台阶。
• 那么到达第十个台阶的方案，是不是就是在到达第九个台阶的方案的基础上全部选择再爬一个台阶呢？
• 除此之外，我还有没有其他可能的选择到达第十个台阶呢？
  • 我是不是可以在第八个台阶上选择一次性上两个台阶，也可以在第九个台阶上选择上一个台阶呢？
  • 答案似乎已经出来了，我们只需要知道有多少中到达和比八个台阶的方案，和多少种到达第九个台阶的方案，就能知道有多少个到达第十个台阶的方案。
  • 值得注意的是，在第八个台阶上，我们可以选择两次爬一个台阶到达楼顶，但这种情况已经被包含在到达第九个台阶的方案当中了，所以不必重复计算。
• 我们可以采用递归的写法，把问题不断抛出，直到达到一个较小的规模。
  • 这里我们把0个台阶的方案也视为一种，因为我们已经在楼顶了，没有其他的选择。

方法一：递归

public int ClimbStairs(int n)
{
    if (n == 0 || n== 1) return 1;

    return ClimbStairs(n - 1) + ClimbStairs(n - 2);
}

• 递归的写法很简单，但这是一个好的解决方案吗？
• 和我们之前写的递归不同，这次我们将一个问题变成了两个问题，随着问题规模的扩大，我们会抛出越来越多的问题，而且这些问题中有相当一部分是重复的。
  • 比如，在计算到达第十个台阶的方案当中，我们先计算了到达第八个台阶和第九个台阶的方案，而在计算到达第九个台阶的方案中，我们计算了到达第八个台阶和到达第七个台阶的方案。
• 我们不想做这些重复的计算，那么有没有办法优化一下呢？我们可以不可以记录一下我们解决过的问题，当我们遇到相同的问题的时候，直接拿答案就好了，没必要进行重复计算。

方法二：记忆化递归

private static Dictionary<int, int> dp = new Dictionary<int, int>();

public int ClimbStairs(int n)
{
    if (n == 0 || n == 1) return 1;

    return dp.ContainsKey(n)? dp [n]: dp[n] = ClimbStairs(n - 1) + ClimbStairs(n - 2);
}

• 我们可以看出，递归本质上是从一个大规模的问题开始，找到一个较小规模的问题，然后利用这个较小规模问题的答案，进一步计算大规模问题的答案，在回归的过程中，一步一步计算问题的答案，只找到最终解决目标问题。
• 那么我们可不可以一开始就从最小规模的问题开始计算呢？

方法三：动态规划

public int ClimbStairs(int n)
{
    var dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i < dp.Length; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

• 既然到达第十个台阶只需要知道到达第八个台阶和第九个台阶的方案即可，那么我们还有必要存储第七个台阶和之前的方案吗？
• 显然，我们可以在空间上也进行一定程度的优化。

方法四：空间压缩

public int ClimbStairs(int n)
{
    int a = 1;
    int b = 1;

    for (int i = 2; i <= n; i++)
    {
        (b, a) = (a + b, b);
    }

    return b;
}

121. 买卖股票的最佳时机

难度：简单

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

解题思路

• 朴素的想法是，穷举所有的可能情况，我们在每一天都尝试买入，在之后的每一天都尝试卖出，最后得到一个最大值。
• 显然，这在问题规模比较大的时候，并不是一个好的方案，我们可否像之前一样对问题进行拆分呢？
• 由于只能买卖一次，我们要想利润最大化，必然需要在历史最低点买入，最高点卖出。
• 我们可以把问题拆分成，每天都尝试卖出，只不过买入的点均为相对于今天的历史最低点，因为我们还不知道明天会是怎样。
• 最后，找到卖出利润的最大值即可。

方法一：递归

public int MaxProfit(int[] prices)
{
    return MaxProfit(prices.Length - 1);

    int MaxProfit(int day)
    {
        if (day <= 0) return 0; // 递归的终点

        var last = MaxProfit(day - 1);
        var today = prices[day] - prices.Take(day).Min(); // 今天-历史最低
        return Math.Max(last, today);
    }
}

• 在上面的方法中，我们每天都计算了一次历史最低值，显然，这一部分中有大量的重复计算，我们可以用一个遍历来维护这个历史最低值。

方法二：记忆化递归

public int MaxProfit(int[] prices)
{
    if (prices.Length < 1) return 0;
    int min = prices[0];

    return MaxProfit(prices.Length - 1);

    int MaxProfit(int day)
    {
        if (day <= 0) return 0;

        var last = MaxProfit(day - 1);
        min = Math.Min(prices[day - 1], min);
        var today = prices[day] - min;

        return Math.Max(last, today);
    }
}

• 换个角度思考一些问题，回归到选择上面，我们每天是不是都有两个选择呢？

  买入或者卖出。

• 由于只能买卖一次，所以在买入之前，我们不能卖出，在卖出之后，我们不能买入也不能卖出。

• 为了方便描述，我们可以定义如下几个状态：

  • 观望状态

  • 已买入状态

  • 已卖出状态

• 一开始，我们处于观望状态，我么不知道要在哪天买入，所以先观望一下。

• 朴素的想法是，要是可以存档就好了，我们可以在今天分别选择买入或者卖出，存两个档，一旦我后悔了，就可以快速读档重新来过。

• 我们新建一个存档库，就叫做DP好了。

  • 我们是不是每一天都需要存两个档呢？表示今天买入了或者今天卖出了。

    DP[i][0] 已买入 DP[i][1] 已卖出 i表示天数
    

  • 那么我存档中存什么数据呢？直观的想法是，存放我们身上持有的资金好了，毕竟最终要求利润最大化，那身上的钱自然是越多越好。

  • 在第一天，我们只能选择买入，故

    DP[0][0] = -prices[0] // 起始资金为0，空手套白狼
    DP[0][1] = 0 // 还没买入，不能卖出，身上一分钱都没
    

  • 在第二天，我们可以选择买入和卖出了，如果买入，那昨天必然没有买入，如果卖出，昨天必然已经买入。

    DP[1][0] = -prices[1] // 还是空手套白狼
    DP[1][1] = prices[1] + DP[0][0] // 卖出获得的钱 + 加上之前欠下的钱
    

  • 稍加思考，我们肯定不能每天都买入，要进行一定的判断，如果今天买入的价格比昨天还高，那我为什么不昨天买？

    DP[1][0] = Max(DP[0][0], -prices[1]) // 昨天买入和今天买入
    

    如果我昨天卖了得到的钱更多，那我为什么不昨天就卖了？反正我是有存档的人，哪天想卖就哪天卖。

    DP[1][1] = Max(prices[1] + DP[0][0], DP[0][1]) // 昨天卖出和今天卖出
    

  • 以此类推，我们可以存完每一天的档。最后一天结束的时候，我们卖出的那个档案一定就是最大利润。

方法三：动态规划

public int MaxProfit(int[] prices)
{

    if (prices.Length < 1) return 0;

    var dp = new int[prices.Length, 2]; // 0已买入，1已卖出
    dp[0, 0] = -prices[0];

    for (int i = 1; i < prices.Length; i++)
    {
        dp[i, 0] = Math.Max(dp[i - 1, 0], -prices[i]); // 昨天买入和今天买入对比
        dp[i, 1] = Math.Max(prices[i] + dp[i - 1, 0], dp[i - 1, 1]); // 昨天卖出和今天卖出对比
    }

    return dp[prices.Length - 1, 1];
}

• 实际上，你已经发现，我们所谓的存档，其实也是记录了一个历史最低值，我们在这个时机买入，在每天都尝试卖出，由于我们只记录一个历史最低值和利润最大值，完全可以不用存那么多档，用两个变量分别记录一下就好。

方法四：空间压缩

public int MaxProfit(int[] prices)
{
    if (prices.Length < 1) return 0;

    var min = prices[0];
    var max = 0;

    for (int i = 1; i < prices.Length; i++)
    {
        if (prices[i] - min > max) max = prices[i] - min;
        if (prices[i] < min) min = prices[i];
    }

    return max;
}

53. 最大子序和

难度：简单

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解题思路

• 朴素的想法是，穷举所有的可能，从每一个元素开始，寻找连续子数组最大和。

• 显然，我们有更好的办法来解决这个问题，经过前两题的操练，我们自然而然的会去尝试动态规划的解法。

• 对于数组中的每一个元素，我们都有两个选择，拿或者不拿。

• 由于题目要求连续子数组，我们选择拿或者不拿会收到一定限制，为了便与描述，我们定义如下状态：

  • 观望状态，此时可以选择拿或者继续观望
  • 拿，此时可以选择继续拿，或者不拿。
  • 不拿，直到结束，我们都不能再拿。

• 一开始，我们处于观望状态，这和之前的股票问题有点相似，而且同样都是只能"买卖"一次。

• 我们依旧可以每天存两个档，0表示不拿，1表示拿，分别记录手中的元素和。

  DP[0][0] = int.MinValue; // 不拿，手中元素和为最小值
  DP[0][1] = nums[0]; // 拿了，值为手中元素和。
  
  

• 第二个元素

  DP[1][0] = Max(DP[0][0], DP[0][1]) // 终止了，从昨天的档案中选一个最大值
  DP[1][1] = Max(DP[0][1] + nums[1], nums[1]) // 接着拿，或者之前在观望，今天开始拿
  
  

• 以此类推，最后我们选择最后一天的存档中，较大的那一个即可。

方法一：动态规划

public int MaxSubArray(int[] nums)
{
    var dp = new int[nums.Length, 2]; // 0 不拿 1 拿
    dp[0, 0] = int.MinValue;
    dp[0, 1] = nums[0];

    for (int i = 1; i < nums.Length; i++)
    {
        dp[i, 0] = Math.Max(dp[i - 1, 0], dp[i - 1, 1]);
        dp[i, 1] = Math.Max(dp[i - 1, 1] + nums[i], nums[i]);
    }

    return Math.Max(dp[nums.Length - 1, 0], dp[nums.Length - 1, 1]);
}

• 很快，我们发现，今天的存档只取决于前一天的存档，我们依旧可以在空间上进行压缩。

方法二：状态压缩

public int MaxSubArray(int[] nums)
{
    var sum = 0;
    var max = nums[0];

    foreach (var item in nums)
    {
        sum = Math.Max(sum + item,item); // 连续和 和 只拿今天的
        max = Math.Max(sum, max);// 当前连续和 和 历史最大和
    }

    return max;
}

最后

• 回顾动态规划的一系列问题，实际上就是从我们暴力枚举的办法中优化掉重复的计算和不必要的空间。
• 除了动态规划的解法之外，本篇中的三道题目都有其他的解法，感兴趣的读者可以思考尝试一下。

• 还没有人评论，欢迎说说您的想法！

相关课程

英特尔® OpenVINO™工具套件初级课程

292956 0元 限免

基于 OpenVINO™ 的 AI 视觉应用进阶课

41904 0元 限免

英特尔 OpenCV 初级认证课程

7676 0元 限免