动态规划例题整理

 

临近毕业找工作的阶段,于是开始刷题。最近在几种刷动态规划类的题目。这篇帖子将会对刷过的一些题做一个整理。里面以Leetcode上的题目为主(其实目前各大平台经典问题几乎都是有交集的)。

P.S. 下面的例题标题如果是链接可以点开看我的可执行代码。

动态规划解题思路和例题

解题思路

最开始我是看了九章算法公开课,所以这里先整理一下这个视频里提出的解题思路。后面各个例题也会按照这个思路进行分析。

动态规划方法虽然比较灵活,但大致可以归纳成以下几个步骤:

  1. 确定状态
    • 研究最优策略的最后一步:确定达到最优策略的最后一步
    • 化为子问题:通过寻找最有状态的前一步状态,来将问题划为“条件一样、规模下降”的子问题。
  2. 状态转移方程
    • 根据子问题的定义来设计:即寻找从前一步到下一步的状态是如何跳转的
  3. 确定初始条件和边界情况:确定在遍历开始前所有已知的初始状态,并且在遍历过程中注意边界情况。
  4. 确定计算顺序
    • 用递推的方法减少重复运算:动态规划高效之根本

先以一道最简单的例题“数塔”为例子。

Leetcode 0120. Triangle

给定一个三角形,寻找一条自顶向下的最短路径。要求是每一步的来源只能是该位置下面一行左右两个位置。例如给定数据:

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

最短路径是11(即,2 + 3 + 5 + 1 = 11)。

我们用上面归纳的四步来分析这道题。

首先,确定状态。由于这个三角形要求每一步的来源只能是下面一行左右两个位置,即T$[i][j]$只能来源于T$[i+1][j]$或者T$[i+1][j+1]$这两个位置。所以我们从下向上找,那么路径的终点就是T$[0][0]$元素。即,此时的最优策略应该是T$[0][0]$是最解。

想要达成最优解,它只有唯二的选择:T$[1][0]$和T$[1][1]$。由于不论选择哪个,直至是在最终结果上加上了T$[0][0]$的值,所以我们只要必须保证T$[1][0]$和T$[1][1]$各自是从起始到当前位置的最优解即可。这就是子问题。

而状态转移方程也是自然而然的:T$[i][j]$ = T$[i][j]$ + min(T$[i+1][j]$, T$[i+1][j+1]$)。即当前位置的之家解,是下一行两个位置最佳解+当前位置值。

接下来我们需要确定初始条件。本题的初始条件起始就是从最下面一行元素开始向上查找。边界条件是当找到第$[0][0]$位置即为最优解。然后根据这个顺序进行递推即可完成。

附上代码:

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        if(triangle.size() == 1){
            return triangle[0][0];
        }
        for (int row = triangle.size() - 2; row >=0 ; --row){
            for (int column = 0; column < row + 1; ++column){
                triangle[row][column] = triangle[row][column] + min(triangle[row + 1][column], triangle[row + 1][column + 1]);
            }
        }
        return triangle[0][0];
    }
};

下面将会分析一些典型例题的解题思路和代码。

0055. Jump Game

给定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。

确定状态

设$j_k$表示在$k$位置最多可以向后跳几步。设$a_k=1$表示能到达位置$k$,$a_k=0$表示不能达到位置$k$。假设一共有N块石头,如果能达到位置N则$a_N=1$。而想要达到这一步的前提是,它的前序步骤(可能不只有唯一的一个前序,不妨设为x)应该是1,而且从前序位置是可以跳跃到这个位置的,即$N - x < j_k$。

状态转移方程

如果想要达到位置N,可以选择从位置0到位置N-1作为前序位置,但这些位置中只有满足可跳跃距离的位置才能够进行跳跃,而且只有当前序位置也是可达位置才能够让这个跳跃序列成立。所以跳跃到位置k是否成立的状态转移方程就是:

上面这个$OR$表示从0开始遍历大括号中的内容,只要遇到任何一个成立即可。

确定初始状态和边界条件

初始状态即第0位置,这个是可达的,所以直接赋值$a_0=1$即可。除遍历终点以外没有其他边界条件。

确定计算顺序

直接从第1个元素开始推导(第0个元素已经赋值$a_0=1$)即可。

代码

class Solution {
public:
    bool canJump(vector<int>& nums) {
        bool result[nums.size()];
        int n = nums.size();
        result[0] = true;
        for (int i = 1; i < n; ++i){
            result[i] = false;
            for (int j = 0; j < i; ++j){
                if (result[j] == true &&i - j <= nums[j]){
                    result[i]=true;
                    break;
                }
            }
        }
        return result[n-1];
    }
};

0062. Unique Paths

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。问总共有多少条不同的路径?

确定状态

最终目标位置是网格中的右下角,即$a_{m,n}$。想要达到这个位置,来源只可能是该位置的上边$a_{m-1,n}$或左边$a_{m,n-1}$。于是可以将问题划分为子问题。

状态转移方程

达到当前位置的可能路径数量,其实就是达到上方一格或者左方一个中各自路径数量之和,即:

初始状态和边界条件

对于第一行和第一列的元素,其路径只会来源于左边(对第一行来说)或上边(对第一列来说),所以他们的初始值都是1,没有其他边界条件。

确定计算顺序

由于每一个位置都依赖于上面和左面一行,所以需要从上到下从左到右的顺序来遍历。

代码

class Solution {
public:
    int uniquePaths(int m, int n) {
        int matrix[m][n];
        for (int i = 0; i < m; ++i){
            matrix[i][0] = 1;
        }
        for (int i = 0; i < n; ++ i){
            matrix[0][i] = 1;
        }
        for (int i = 1; i < m; ++ i){
            for (int j = 1; j <n; ++ j){
                matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1];
            }
        }
        return matrix[m - 1][n - 1];
    }
};

0063. Unique Paths II

这道题和上面提到的0062. Unique Paths非常相似。唯一的区别在于这里出现了“墙”这种东西。在状态转移方程中要加入对墙的判断,代码如下:

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        int64_t matrix[m][n];
        matrix[0][0] = 1 - obstacleGrid[0][0];

        for (int i = 1; i < n; ++ i){
            matrix[0][i] = (1 - obstacleGrid[0][i]) * matrix[0][i-1];
        }

        for (int i = 1; i < m; ++i){
            matrix[i][0] = (1 - obstacleGrid[i][0]) * matrix[i-1][0];
        }
        
        for (int i = 1; i < m; ++ i){
            for (int j = 1; j <n; ++ j){
                matrix[i][j] = (1 - obstacleGrid[i][j]) * (matrix[i - 1][j] + matrix[i][j - 1]);
            }
        }
        return matrix[m - 1][n - 1];
    }
};

0322. Coin Change

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。 示例 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1

示例 2:

输入: coins = [2], amount = 3
输出: -1

确定状态

假设组成金额为$k$,最终最优的结果为$a_k$个硬币。那么对达到最优状态之前分别有三种(对于第一个用例)可能:即$a_{k-1}$、$a_{k-2}$和a_{k-5}。而这三个则分别都是子问题。

状态转移方程

对于这道题的第一个用例(三种面值)来说

初始状态和边界条件

这道题可以以0作为初始条件:即组成0元需要0枚硬币。然后从1开始向后递推。此时有一个边界条件:即拼出当前金额需要大于所使用的货币面值。同时我们可以用MAX来表示当前面值不可能拼出来。

确定计算顺序

从1开始进行递推。

代码

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int MAX = INT32_MAX;
        int d[amount + 1];
        d[0] = 0;
        for (int i = 1; i <= amount; ++i){
            int current_result = MAX;
            for (int j = 0; j < coins.size(); ++j){
                if (i >= coins[j] && d[i - coins[j]] != MAX){
                    current_result = min(current_result, d[i - coins[j]]+1);
                }
            }
            d[i] = current_result;
        }
        return d[amount] == MAX ? -1 : d[amount];
    }
};

股票交易

0121. 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。

这道题可以暴力搜索:即便利每一个买入和卖出日,计算最高获利,负责度是$O(n^2)$。也可以动态规划,复杂度是$O(n)$。

如果用DP的方法则考虑每一天能够获得最高价格和之间的关系。所以此时状态是当日价格$a_k$,对于每一天$k$来说,最高的获利只有两种情况:1是前一天已经把股票卖出了,所以是前一天的获利。2是当天股票价格减购入时的股票价格(而且要求购入价格应该是之前所有天里最少的那一天)。于是状态转移方程是:

其中一个可以优化的是最低的购买价格可以在遍历状态的时候随时保存下来。初始条件是$a_0=0$因为第0天买了但是首日不允许卖出。然后从$a_1$开始向后递推即可。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0){
            return 0;
        }
        int min_price = prices[0];
        int f[prices.size() + 1];
        f[0] = 0;
        for (int i = 1; i < prices.size() + 1; ++i){
            min_price = min(min_price, prices[i - 1]);
            f[i] = max(f[i - 1], prices[i - 1] - min_price);
        }
        return f[prices.size()];
    }
};

0122. Best Time to Buy and Sell Stock II

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
     因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

这道题其实是用贪心法,但贪心也算是动态规划的一种特例。

其实这道题的核心在于,最高的总获利,一定是整条股价波动曲线所有上升区间的和。即只要昨天价格比今天低,就在昨天买入,今天卖出。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0){
            return 0;
        }
        int accumulate = 0;
        for (auto it = prices.begin(); it != prices.end() - 1; ++it){
            int diff = *(it + 1) - (*it);
            if (diff > 0){
                accumulate += diff;
            }
        }
        return accumulate;
    }
};

0123. Best Time to Buy and Sell Stock III

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。
     随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3 。

示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。   
     因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1] 
输出: 0 
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

这道题与前两道题相比就要难得多了。主要是这里有“最多交易两笔”的限制。我们可以将“两笔”也加入到状态之中。而且还需要对“两笔”进行细分。观察整个购买过程,一共可能存在着5种不同的交易阶段:

  • 阶段0:0次买入0次卖出,无持股
  • 阶段1:1次买入0次卖出,有持股
  • 阶段2:1次买入1次卖出,无持股
  • 阶段3:2次买入1次卖出,有持股
  • 阶段4:2次买入2次卖出,无持股

这五个阶段可能在购买序列之中出现,但每新到一个交易日,或者保持前一日的阶段不改变,或者从前一日的阶段向后增加一步。不可能出现跳两步或者向之前的阶段跳转。明白了这个阶段设计之后,我们就能将状态设计成二维矩阵$f[i][k]$,表示到第$i$天时如果处于$k$阶段情况下能赚到的最多的钱。

然后我们再来分析处于不同阶段时的决策。

  • 当处于阶段0时,不论现在是第几天,赚到的钱都是0。因为手里没有买入过股票,也没有卖出过股票。
  • 当处于阶段1时,手里赚到的钱只会有两个来源:1是“阶段切换过(即昨天处于阶段0,今天处于阶段1,即昨天没有持有股票,今天买入)”时,前一天在上一阶段赚到的钱$f[i-1][j-1]$。2是“保持阶段(即昨天也处于阶段1)”,那么今天能“赚”到的最多的钱就是股票昨天的价格减前天的价格$p_{i-1}-p{i-2}$,加上直到昨天赚到的钱$f[i-1][j]$。而今天能赚到的钱$f[i][j]$就是选择这两个来源中较大的那个。
  • 当处于阶段2时,手里赚到的钱仍然有两个来源:1是“阶段切换过(即昨天处于阶段1,今天处于阶段2)”时前一天在上一阶段赚到的钱$f[i-1][j-1]$加上今天股票卖出(因为这个阶段切换就是在卖股票)时赚到的钱$p_{i-1}-p_{i-2}$。2是保持昨天的阶段的钱(此时由于手中不持有股票,所以并不会有单日盈余)$f[i-1][j]$。
  • 当处于阶段3时,和处于阶段1时的情况一样。
  • 当处于阶段4时,和处于阶段2时的情况一样。

上面加粗的是在说,此时的收益实际上只记录前一天的变化,这样在向后递推的时候,每次相当于只计算一个小阶段,而不是从首日开始累加,不然会导致获利被重复计算,结果就错了。而加了引号的“赚”是指,前后两天价格差其实有可能是负数,也仍然记录在内参与累加。

最终我们可以把状态转移方程整理一下:

对于状态2、4来说,都是下面这个:

而对于状态1、3来说则应该是:

同时,还需要有几个边界条件:首先当$f[\cdot][0]=0$因为无论是第几天,如果处于阶段0,都不会有盈利。第二是$f[0][i]_{i=1\dots4}=-\infty$,因为第0天时是不可能处于除阶段0以外的其他阶段的。

然后就从$i=1$到$k$,$j=0$到$5$进行递推即可。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0){
            return 0;
        }
        int f[prices.size() + 1][5];
        f[0][0] = 0;
        f[0][1] = f[0][2] = f[0][3] = f[0][4] = INT32_MIN / 2;  // small but not overflow
        f[1][0] = 0;
        f[1][1] = 0;
        f[1][2] = f[1][3] = f[1][4] = INT32_MIN / 2;
        for (int i = 2; i < prices.size() + 1; ++i){
            f[i][0] = f[i - 1][0];
            f[i][1] = max(f[i - 1][1] + prices[i - 1] - prices[i - 2], f[i - 1][0]);
            f[i][2] = max(f[i - 1][2], f[i - 1][1] + prices[i - 1] - prices[i - 2]);
            f[i][3] = max(f[i - 1][3] + prices[i - 1] - prices[i - 2], f[i - 1][2]);
            f[i][4] = max(f[i - 1][4], f[i - 1][3] + prices[i - 1]- prices[i - 2]);
        }
        return max(max(f[prices.size()][0], f[prices.size()][2]), f[prices.size()][4]);
    }
};

0188. Best Time to Buy and Sell Stock IV

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 = 4-2 = 2 。

示例 2:

输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后,在第 5 天 (股票价格 = 0) 的时候买入,在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

这道题本质上其实和上面的0123. Best Time to Buy and Sell Stock III是完全一样的,唯一的区别就是在0123种要求最多进行两次交易,而这道题则是$k$次。所以里面一共包含了$2*k+1$个阶段。直接将上一道题的数组和递推范围扩大即可解答。

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if (prices.size() == 0){
            return 0;
        }
        if (prices.size() == 1){
            return 0;
        }
        if (k > prices.size() / 2){
            int acc = 0;
            for (int i = 1; i < prices.size(); ++i){
                acc += max(prices[i] - prices[i - 1], 0);
            }
            return acc;
        }

        int f[prices.size() + 1][k * 2 + 1];
        f[0][0] = 0;
        for (int i = 1; i < k * 2 + 1; ++i){
            f[0][i] = INT32_MIN / 2;
        }
        

        for (int i = 1; i < prices.size() + 1; ++i){
            for (int j = 0; j < k * 2 + 1; ++j){
                if (j % 2 == 0){ // current don't hold stock
                    f[i][j] = max(f[i - 1][j], j >= 1 && i >= 2? f[i - 1][j - 1] + prices[i - 1] - prices[i - 2] : INT32_MIN / 2);
                }else{ // current hold stock
                    f[i][j] = max(i >= 2? f[i - 1][j] + prices[i - 1] - prices[i - 2]: INT32_MIN / 2, j >= 1 ? f[i][j - 1] : INT32_MIN / 2);
                }
            }
        }

        int result = INT32_MIN;
        for (int i = 0; i < k * 2 + 1; i += 2){
            result = max(result, f[prices.size()][i]);
        }
        return result;
    }
};

House Robber

0198. 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 。

我们可以设$f[i]$表示前$i$天能够偷到的最大金额(最优解)。而由于这道题的一个限制是不能偷窃相邻两间房屋,所以对于最优解来说,它要么是前一天的最优解且第当天不偷窃(即等于$f[i-1]$),要么是当天偷窃的获利加两天前偷窃的最优解,于是就有了状态转移方程:

初始条件是前0天窃得0元,前1天窃得$num[0]$元。然后就可以进行递推了。

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0){
            return 0;
        }else if (nums.size() == 1){
            return nums[0];
        }else if (nums.size() == 2){
            return max(nums[0], nums[1]);
        }
        
        int result[nums.size() + 1];
        result[0] = 0;
        result[1] = nums[0];
        result[2] = max(nums[0], nums[1]);
        for (int i = 3; i < nums.size() + 1; ++i){
            result[i] = max(result[i - 1], result[i - 2] + nums[i - 1]);
        }
        return result[nums.size()];
    }
};

0213. House Robber II

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

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

示例 1:

输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。

示例 2:

输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

这道题相比0198. House Robber多了一个要求:首尾相连成环。我的方法是分别对待“取第一个房子”和“不取第一个房子”。即把这道题拆成两道0198. House Robber:一共有N栋房子,拆成$0\approx N-2$和$1\approx N-1$两道分别有$N-1$栋房子的题来做。

这里需要注意的是初始条件和边界条件。对于“从第0到第N-2栋房子”的情况,初始条件和正常情况一样,都是$f[0]=0$,$f[1]=nums[0]$。但最后一天由于被排除,所以最后一天不再是从原有的两个选项中挑大的,而是直接等于前一天的结果,相当于跳过了最后一天。而对于“从第1到第N-1栋房子”的情况来说,边界和正常条件一样,但由于第一天被排除,所以$f[0]=0$且$f[1]=0$(因为前1天不允许偷窃,所以前1天的获利也是0)。

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0){
            return 0;
        }else if (nums.size() == 1){
            return nums[0];
        }else if (nums.size() == 2){
            return max(nums[0], nums[1]);
        }

        int f_keep[nums.size() + 1];
        int f_drop[nums.size() + 1];

        f_keep[0] = 0;
        f_keep[1] = nums[0];

        f_drop[0] = 0;
        f_drop[1] = 0;

        for (int i = 2; i < nums.size() + 1; ++i){
            if (i != nums.size()){
                f_keep[i] = max(f_keep[i - 1], f_keep[i - 2] + nums[i - 1]);
            }else{
                f_keep[i] = f_keep[i - 1];
            }
            f_drop[i] = max(f_drop[i - 1], f_drop[i - 2] + nums[i - 1]);
        }
        return max(f_keep[nums.size()], f_drop[nums.size()]);
    }
};

Paint House

0256. Paint House

假如有一排房子,共 n 个,每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种,你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然,因为市场上不同颜色油漆的价格不同,所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的矩阵来表示的。

例如,costs[0][0] 表示第 0 号房子粉刷成红色的成本花费;costs[1][2] 表示第 1 号房子粉刷成绿色的花费,以此类推。请你计算出粉刷完所有房子最少的花费成本。

注意:

所有花费均为正整数。

示例:

输入: [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色,1 号房子粉刷成绿色,2 号房子粉刷成蓝色。
     最少花费: 2 + 5 + 3 = 10。

这道题可以将颜色作为状态的一部分,考虑颜色之间的限制关系作为递推的路径。一共三种颜色,所以就包括了三种状态:$f[i][j]$表示将第$i$栋房子粉刷成第$j$种颜色的最低成本。在进行状态转移的时候有一个限制就是:当前房子的粉刷成本不能来源于前一栋粉刷成同样颜色的房子。于是可以把状态转移方程写成这样:

初始条件是第0栋房子刷成各自颜色的价格。

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        if (costs.size() == 0){
            return 0;
        }
        int f[costs.size()][costs[0].size()];
        for (int j = 0; j < costs[0].size(); ++j){
            f[0][j] = costs[0][j];
        }
        for (int i = 1; i < costs.size(); ++i){
            for (int j = 0; j < costs[0].size(); ++j){
                int t = INT32_MAX;
                for (int k = 0; k < costs[0].size(); ++k){
                    if (j == k){ // skip the same color
                        continue;
                    }
                    t = min(t, f[i - 1][k]);
                }
                f[i][j] = t + costs[i][j];
            }
        }
        
        int m = INT32_MAX;
        for (int j = 0; j < costs[0].size(); ++j){
            m = min(m, f[costs.size() - 1][j]);
        }
        return m;
    }
};

0265. Paint House II

假如有一排房子,共 n 个,每个房子可以被粉刷成 k 种颜色中的一种,你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然,因为市场上不同颜色油漆的价格不同,所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x k 的矩阵来表示的。

例如,costs[0][0] 表示第 0 号房子粉刷成 0 号颜色的成本花费;costs[1][2] 表示第 1 号房子粉刷成 2 号颜色的成本花费,以此类推。请你计算出粉刷完所有房子最少的花费成本。

注意:

所有花费均为正整数。

示例:

输入: [[1,5,3],[2,9,4]]
输出: 5
解释: 将 0 号房子粉刷成 0 号颜色,1 号房子粉刷成 2 号颜色。最少花费: 1 + 4 = 5; 
     或者将 0 号房子粉刷成 2 号颜色,1 号房子粉刷成 0 号颜色。最少花费: 3 + 2 = 5. 

进阶: 您能否在 O(nk) 的时间复杂度下解决此问题?

这道题和0256. Paint House相比难点在于要求时间复杂度是$O(n*k)$,而不是$O(n * k * k)$。从状态转移方程来看其实并不需要遍历前一次粉刷中所有的房子,而是只需要将其中最小和次小保存起来即可。当粉刷到当前颜色时,如果和前一栋房子最小的粉刷颜色不一样(即说明现在可以用前一栋房子最小cost加当前颜色),则用最小。否则用次小。这道题比较麻烦的地方是要维护最小和次小,同时还要有两套临时变量交替使用(新遍历寻找最小和次小的过程中,不能影响上一栋房子找到的最小和次小)。

下面这个代码其实有点儿麻烦了,我是把两次循环(一次用来找最小次小值、一次用来更新)合并到了一起。

class Solution {
public:
    int minCostII(vector<vector<int>>& costs) {
        int n = costs.size();
        if (n == 0){
            return 0;
        }
        int k = costs[0].size();
        if (k == 0){
            return 0;
        }

        int f[n][k];

        for (int j = 0; j < k; ++j){
            f[0][j] = costs[0][j];
        }

        for (int i = 1; i < n; ++i){
            int last_cost = INT32_MAX;
            int last_color = -1;
            int second_to_last_cost = INT32_MAX;
            int second_to_last_color = -1;

            for (int j = 0; j < k; ++j){
                if (f[i - 1][j] < last_cost){
                    second_to_last_cost = last_cost;
                    second_to_last_color = last_color;
                    last_cost = f[i - 1][j];
                    last_color = j;
                }else{
                    if (f[i - 1][j] < second_to_last_cost){
                        second_to_last_cost = f[i - 1][j];
                        second_to_last_color = j;
                    }
                }
            }

            for (int j = 0; j < k; ++j){

                if (j != last_color){
                    f[i][j] = last_cost + costs[i][j];
                }else{
                    f[i][j] = second_to_last_cost + costs[i][j];
                }
            }
            
        }

        int current_min = f[n - 1][0];
        for (int i = 1; i < k; ++i){
            current_min = min(current_min, f[n - 1][i]);
        }
        return current_min;
    }
};

最长子序列

0005. Longest Palindromic Substring

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2:

输入: "cbbd"
输出: "bb"

注意:这道题要求的是最长回文子串(和子序列不同,子串要求是连续的)

由于要求是回文子串,那么对于一个子串$S=\left[s_1,s_2,\dots,s_n\right]$来说,如果它是一个回文的,显然有$s_1=s_n$,且由$\left[s_2,\dots,s_{n-1}\right]$组成的子串也必然是回文的。我们不妨用$f[i][j]$从第$i$到第$j$个字符组成的子串是否是回文的。那么状态转移方程就是:

即当这个字符串掐头去尾的子串是回文的且这个字符串首位字母相等时,这个字符串就是回文的,否则就不是回文的。不过在递推的时候我们发现这道题的依赖关系和以往的“从左到右”、“从上到下”的顺序不同,而是“从内到外”。所以我们可以以“起始位置”和“长度”作为遍历的顺序。这个过程类似回文串的生成过程:先从长度是1的所有子串(即都是字符,且都是回文子串)开始,然后遍历长度是2的子串(当前后两个字符相等时即是回文)。当有了这两种长度的子串后,所以长度的子串都可以这样向后递推。由于这道题想知道的是最长子串,所以在生成子串的过程中时刻记住最长的那个子串的起始位置,最后返回这个子串即可。

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.length() <= 1){
            return s;
        }

        bool p[s.length()][s.length()];
        for (int i = 0; i < s.length(); ++i){
            for (int j = 0; j < s.length(); ++j){
                if (i == j){
                    p[i][j] = true;
                }else{
                    p[i][j] = false;
                }
            }
        }

        int best_from = 0;
        int best_to = 0;
        int best_len = 1;

        for (int i = 1; i < s.length(); ++i){
            if (s[i - 1] == s[i]){
                best_from = i - 1;
                best_to = i;
                best_len = 2;
                p[i - 1][i] = true;
            }
        }
        
        for (int l = 2; l <= s.length(); ++l){
            for (int i = 0; i < s.length() - l; ++i){
                int j = i + l;
                if (s[i] == s[j] && p[i + 1][j - 1] == true){
                    p[i][j] = true;
                    if (j - i + 1 > best_len){
                        best_from = i;
                        best_to = j;
                    }
                }else{
                    p[i][j] = false;
                }
            }
        }
        string result = "";
        for (int i = best_from; i <= best_to; ++i){
            result = result + s[i];
        }
        return result;
    }
};

0300. Longest Increasing Subsequence

给定一个无序的整数数组,找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

说明:

  • 可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。
  • 你算法的时间复杂度应该为 $O(n^2)$ 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

传说中的LIS问题,要求的是最长上升子序列,不是子串,所以不要求连续。下面这个利用DP的方法是$O(n^2)$的复杂度。

首先我们考虑最优解$f[i]$表示截止到第$i$个数字,最大的上升子序列长度。那么这个最优解是从哪里来的?它一定来源于之前某一个比数字$nums[i]$要小的$nums[k]$(即$k\le i$)+1。也就是说,当我们在寻找第$i$个数字对应的最长LIS时,我们应该找到所有它的子序列+1,并且从其中挑一个最大的。当然,如果之前所有的数字都比$nums[i]$大,那么这个位置的最长子序列长度就是1(表示只有这个元素本身)。那么状态转移方程可以写成:

本题没有初始状态(或者说第0个数的最长子序列是1)。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() == 0){
            return 0;
        }
        vector<int> result = {};
        for (int i = 0; i < nums.size(); ++i){
            result.push_back(1);
            for (int j = 0; j < i; j += 1){
                if (nums[j] < nums[i]){
                    result[i] = max(result[i], result[j] + 1);
                }
            }
        }
        int m = -1;
        for (int i = 0; i < nums.size(); ++i){
            m = max(m, result[i]);
        }
        return m;
    }
};

0354. Russian Doll Envelopes

给定一些标记了宽度和高度的信封,宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。

请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。

说明: 不允许旋转信封。

示例:

输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出: 3 
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

这道题其实本质上还是LIS问题。因为首先信封不允许旋转,然后信封可以交换顺序(即信封本身无序)。所以我们可以先沿着一个维度从小到大排序之后,再按照LIS问题处理。只不过最原始的LIS要求后面的元素比前面的元素大。而此时要求后面的信封在两个维度上的尺寸都要大于前面的信封,其他就完全一样了。

尽管这道题在leetcode上是困难,但实际上“不允许旋转信封”、“信封无顺序”、“要求长宽都大于而非大于等于”其实都降低了本题的难度。

class Solution {
public:
    static bool sort_func(vector<int> a, vector<int> b){
        if (a[0] == b[0]){
            return a[1] < b[1];
        }
        return a[0] < b[0];
        
    }

    int maxEnvelopes(vector<vector<int>>& envelopes) {
        if (envelopes.size() == 0){
            return 0;
        }
        sort(envelopes.begin(), envelopes.end(), sort_func);

        int f[envelopes.size()];
        f[0] = 1;
        for (int i = 1; i < envelopes.size(); ++i){
            f[i] = 1;
            for (int j = 0; j < i; ++j){
                if (envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]){
                    f[i] = max(f[i], f[j] + 1);
                }
            }
        }
        int result = -1;
        for (int i = 0; i < envelopes.size(); ++i){
            result = max(result, f[i]);
        }
        return result;
    }
};

背包

背包类问题通常都需要用二维数组表示状态。其中第一维表示序列,第二维表示“组成重量”。

0416. Partition Equal Subset Sum

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

注意:

  1. 每个数组中的元素不会超过 100
  2. 数组的大小不会超过 200

示例 1:

输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.

这道题其实是最基本的背包类型的问题。所谓的两个子集,其实就是从所有元素中挑一部分。所谓的使两个子集元素和相等,就是挑出来的元素和等于所有元素和的二分之一。于是我们设计这样的状态:$f[i][w]$表示是否能够从前$i$件物品(元素)中挑出一部分,组成刚好是$w$的重量(元素和)。而想要满足这个要求(即让$f[i][w]=true$)需要考虑两种可能:即是否把物品$i$放进背包中。如果不放物品$i$,那是否可行就要看$f[i-1][w]$。(此时$w$无变化,因为如果不放物品$i$,那组成的重量也就没有变化)。如果选择放入了这个物品,那么就要看“放入这件物品之前,即$f[i-1][w-nums[i - 1]]$”是否为true。

于是状态转移方程就是:

然后初始条件是$f[0][0]=true$认为用0件物品组成重量为0的元素是可行的。而$f[0][k]=false|k>0$因为用0件物品无法组成任何其他重量。最终答案就是$f[N][sum/2]$其中(sum)是商品重量和。背包问题尤其需要注意边界条件问题。因为在计算后面一项的时候,有可能与前面任何一项有关联,在计算前项下标时有可能小于0。例如当前物品重量100,那么在计算组成总重量为10的前项时应该就直接忽略(=false)。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (int i = 0; i < nums.size(); ++i){
            sum += nums[i];
        }
        if (sum % 2 == 1){
            return false;
        }

        int f[nums.size() + 1][sum / 2 + 1];
        f[0][0] = true;
        for (int i = 1; i < sum / 2 + 1; ++i){
            f[0][i] = false;
        }

        for(int i = 1; i < nums.size() + 1; ++i){
            for (int j = 0; j <= sum / 2; ++j){
                f[i][j] = f[i - 1][j] || (nums[i - 1] <= j ? f[i - 1][j - nums[i - 1]] : false);
            }
        }

        return f[nums.size()][sum / 2];
    }
};

未分类

0064. Munimum Path Sum

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        if (m == 0){
            return 0;
        }
        int n = grid[0].size();
        if (n == 0){
            return 0;
        }
        for (int i = 1; i < n; ++i){
            grid[0][i] += grid[0][i - 1];
        }
        for (int i = 1; i < m; ++i){
            grid[i][0] += grid[i - 1][0];
        }

        for (int r = 1; r < grid.size(); ++r){
            for (int c = 1; c < grid[0].size(); ++c){
                grid[r][c] += min(grid[r - 1][c], grid[r][c - 1]);
            }
        }
        return grid[m - 1][n - 1];
    }
};

0091. Decode Ways

class Solution {
public:
    int numDecodings(string s) {
        if (s.length() == 0 or s[0] == '0'){
            return 0;
        }
        if (s.length() == 1){
            return 1;
        }


        int l[s.length()];
        l[0] = 1;

        if (is_valid(s[0], s[1])){
            if (s[1] == '0'){
                l[1] = 1;
            }else{
                l[1] = 2;
            }
        }else{
            if (s[1] == '0'){
                l[1] = 0;
            }else{
                l[1] = 1;
            }
        }

        for (int i = 2; i < s.length(); ++i){
            l[i] = 0;

            if (s[i - 1] == '0' && s[i] == '0'){
                return 0;
            }

            if (!is_valid(s[i - 2], s[i - 1]) && !is_valid(s[i - 1], s[i]) && l[i-1] == 0){
                return 0;
            }

            if (is_valid(s[i - 1], s[i])){
                l[i] += l[i - 2];
            }

            if (s[i] != '0'){
                l[i] += l[i - 1];
            }
            
            
        }
        return l[s.length() - 1];
    }

    bool is_valid(char n1, char n2){
        int n = (n1 - '0') * 10 + n2 - '0';
        if (n >= 10 && n <= 26){
            return true;
        }
        return false;
    }
};

0132. Palindrome Partitoing II

class Solution {
public:
    int minCut(string s) {
        bool p[s.length()][s.length()];
        for(int i = 0; i < s.length(); ++i){
            for (int j = 0; j < s.length(); ++j){
                p[i][j] = false;
            }
        }
        // odd pal num
        for (int i = 0; i < s.length(); ++i){
            for (int j = 0; i - j >= 0 && i + j <= s.length(); ++j){
                if (s[i - j] == s[i + j]){
                    p[i - j][i + j] = true;
                }else{
                    break;
                }
            }
        }

        // even pal num
        for (int i = 1; i < s.length(); ++i){
            for(int j = 1; i - j >=0 && i + j <= s.length() + 1; ++j){
                if (s[i - j] == s[i + j - 1]){
                    p[i - j][i + j - 1] = true;
                }else{
                    break;
                }
            }
        }

        // dp
        int f[s.length() + 1];
        f[0] = 0;
        for (int i = 1; i <= s.length(); ++i){
            int m = INT32_MAX;
            for (int j = 0; j < i; ++j){
                if (p[j][i - 1] == true){
                    m = min(m, f[j]);
                }
            }
            f[i] = m + 1;
        }
        return f[s.length()] - 1;
    }
};

0152. Maximum Product Subarray

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int length = nums.size();
        int f[length];  // max
        int g[length];  // min
        f[0] = nums[0];
        g[0] = nums[0];

        for (int i = 1; i < nums.size(); ++i){
            f[i] = max(nums[i], max(nums[i] * f[i - 1], nums[i] * g[i - 1]));
            g[i] = min(nums[i], min(nums[i] * f[i - 1], nums[i] * g[i - 1]));
        }
        int m = INT32_MIN;
        for (int i = 0; i < nums.size(); ++i){
            m = max(f[i], m);
        }
        return m;
    }
};

0279. Perfect Squares

class Solution {
public:
    int numSquares(int n) {
        if (n == 0){
            return 0;
        }
        int result[n + 1];
        result[0] = 0;
        for (int i = 1; i <= n; ++i){
            int m = INT32_MAX;
            for (int j = 1; j * j <= i; ++j){
                m = min(m, result[i - j * j]);
            }
            result[i] = m + 1;
        }
        return result[n];
    }
};

0338. Counting Bits

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> result;
        result.push_back(0);
        for (int i = 1; i < num + 1; ++i){
            result.push_back(result[i >> 1] + (i % 2));
        }
        return result;
    }
};

0361. Bomb Enemy

class Solution {
public:
    int maxKilledEnemies(vector<vector<char>>& grid) {
        int m = grid.size();
        if (m == 0){
            return 0;
        }
        int n = grid[0].size();
        if (n == 0){
            return 0;
        }
        int up[m][n];
        int down[m][n];
        int left[m][n];
        int right[m][n];

        //up
        for (int i = 0; i < n; ++i){
            up[0][i] = 0;
            if (grid[0][i] == 'E'){
                up[0][i] = 1;
            }
        }
        for (int r = 1; r < m; ++r){
            for (int c = 0; c < n; ++c){
                if(grid[r][c] == '0'){
                    up[r][c] = up[r - 1][c];
                }else if(grid[r][c] == 'E'){
                    up[r][c] = up[r - 1][c] + 1;
                }else if(grid[r][c] == 'W'){
                    up[r][c] = 0;
                }
            }
        }

        //down
        for (int i = 0; i < n; ++i){
            down[m - 1][i] = 0;
            if (grid[m - 1][i] == 'E'){
                down[m - 1][i] = 1;
            }
        }

        for (int r = m - 2; r >= 0; --r){
            for (int c = 0; c < n; ++c){
                if(grid[r][c] == '0'){
                    down[r][c] = down[r + 1][c];
                }else if(grid[r][c] == 'E'){
                    down[r][c] = down[r + 1][c] + 1;
                }else if(grid[r][c] == 'W'){
                    down[r][c] = 0;
                }
            }
        }

        //left
        for (int i = 0; i < m; ++i){
            left[i][0] = 0;
            if (grid[i][0] == 'E'){
                left[i][0] = 1;
            }
        }

        for (int c = 1; c < n; ++c){
            for (int r = 0; r < m; ++r){
                if(grid[r][c] == '0'){
                    left[r][c] = left[r][c - 1];
                }else if(grid[r][c] == 'E'){
                    left[r][c] = left[r][c - 1] + 1;
                }else if(grid[r][c] == 'W'){
                    left[r][c] = 0;
                }
            }
        }

        //right
        for (int i = 0; i < m; ++i){
            right[i][n - 1] = 0;
            if (grid[i][n - 1] == 'E'){
                right[i][n - 1] = 1;
            }
        }

        for (int c = n - 2; c >= 0; --c){
            for (int r = 0; r < m; ++r){
                if(grid[r][c] == '0'){
                    right[r][c] = right[r][c + 1];
                }else if(grid[r][c] == 'E'){
                    right[r][c] = right[r][c + 1] + 1;
                }else if(grid[r][c] == 'W'){
                    right[r][c] = 0;
                }
            }
        }

        // aggregate
        int current_max = 0;
        for (int i = 0; i < m; ++i){
            for (int j = 0; j < n; ++j){
                if (grid[i][j] == '0'){
                    current_max = max(current_max, up[i][j] + down[i][j] + left[i][j] + right[i][j]);
                }
            }
        }
        return current_max;
    }
};

0410. Split Array Largest Sum

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        if (m == 0 || nums.size() == 0){
            return 0;
        }
        long f[m + 1][nums.size() + 1];
        long sum[nums.size()][nums.size()];
        // int sum[5][5];
        for (int i = 0; i < nums.size(); ++i){
            long acc = 0;
            for (int j = i; j < nums.size(); ++j){
                acc += nums[j];
                sum[i][j] = acc;
            }
        }

        f[0][0] = 0;
        for (int i = 1; i <= nums.size(); ++i){
            f[0][i] = INT32_MAX;
        }
        for (int i = 0; i < m; ++i){
            f[i][0] = 0;
        }

        for (int k = 1; k <= m; ++k){
            for (int i = 1; i <= nums.size(); ++i){
                long t_min = INT32_MAX;
                for (int j = 0; j < i; ++j){
                    t_min = min(t_min, max(f[k - 1][j], sum[j][i - 1]));
                }
                f[k][i] = t_min;
            }
        }

        return f[m][nums.size()];
    }
};

参考资料

  1. 九章算法公开课
  2. 我的Leetcode刷题代码库
  3. 一篇Leetcode上比较好的对股票系列六道题问题的分析