算法(二)

发表于2022-06-14更新于2023-04-25字数统计5k阅读时长34分阅读次数

前言

本文还是算法知识的整理记录博客，主题是动态规划。由于近期接触的更多是C++，且我认为 C++ 标准库中容器设计较java更简洁易用，所以本文使用 C++ 为例。和上篇算法一样，借助leetcode中题作为例子，此外动态规划思想不难，但是题目纷繁复杂，有时很难找到状态变量的选取，因此文中只是举部分有代表性的例子。

动态规划

动态规划(Dynamic Programming)通过组合子问题的解来求解原问题。分治法也是通过求解子问题的解来得到原问题的解，不同的是，分治法的子问题之间互不相交；而动态规划中的子问题中很多是重叠的，故可以采用以空间换时间的方法来优化时间复杂度。实际上动态规划算法的本质是表格法，通过表格来记录已经求解过的子问题的解，后续可以通过查表的方式直接得到子问题的解。

求解动态规划的关键步骤为：

  1. 刻画一个最优解的结构特征，即如何将原问题分解成一系列子问题，并通过响应的状态量来记录子问题的解。
  2. 找到状态转移方程，也就是不同状态量之间的转换关系，这个转移方程刻画了原问题和子问题之间的关系。这是最重要的一步。
  3. 自底向上的求解问题，也就是先解决小问题，一步步解决原问题。

比较抽象，下面举些例子。

一维动态规划

70. 爬楼梯

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

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

解：这是一道非常经典又简单的动态规划题，定义状态量dp[i]表示i阶台阶的楼梯共有多少种不同的方法，其与子问题之间的状态转移方程显然为：

dp[i]=dp[i−1]+dp[i−2]dp[i] = dp[i-1] + dp[i-2]

也就是说，爬上第i个台阶的方法为爬上第i-1个台阶的方法和爬上第i-2个台阶的方法之和，因为第i个台阶可以从第i-1个台阶或第i-2个台阶一次性爬上来。还有一个有意思的现象就是，这个转移方程得到的数列就是斐波那契数列。

1
2
3
4
5
6
7
8
9
10
11
int climbStairs(int n) {
    vector<int> dp(n, 1);
    for(int i=1; i<n; ++i)
    {
        if(i == 1)
            dp[i] = 2;
        else
            dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n-1];
}

另外，由于每个状态之和前两个状态有关，可以不用定义长度为 n 的数组以压缩空间：

1
2
3
4
5
6
7
8
9
10
11
12
int climbStairs(int n) {
    if (n <= 2) {
        return n;
    }
    int c1 = 1, c2 = 2, c3 = 3;
    for (int i=3; i<=n; ++i) {
        c3 = c1 + c2;
        c1 = c2;
        c2 = c3;
    }
    return c3;
}

413. 等差数列划分

如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。

例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。

子数组 是数组中的一个连续序列。

解：这里用dp[i]表示以nums[i-1]结尾的等差数列个数，当nums[i-1]*2 == nums[i-2] + nums[i]时，有：

dp[i]=dp[i−1]+1;dp[i] = dp[i-1] + 1;

需要注意的是最终求解的是所有dp[i]的和：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int numberOfArithmeticSlices(vector<int>& nums) {
    int n = nums.size();
    if (n < 3) {
        return 0;
    }
    int res = 0;
    vector<int> dp(n, 0);
    for (int i=2; i<n; ++i) {
        if (nums[i-1]*2 == nums[i-2] + nums[i]) {
            dp[i] = dp[i-1] + 1;
        }
        res += dp[i];
    }
    return res;
}

同样可以压缩空间，不妨试试。

二维动态规划

221. 最大正方形

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

解：用dp[i][j]表示以下标 i,j 为右下角元素的最大正方形的边长，这个边长和dp[i-1][j-1]以及dp[i-1][j]、dp[i][j-1]相关。其边长为后三者中最小边长+1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int maximalSquare(vector<vector<char>>& matrix) {
    int m = matrix.size();
    int n = matrix[0].size();
    int res = 0;
    // dp[i][j]为以i,j为右下角的正方形的最大边长
    vector<vector<int>> dp(m, vector<int>(n, 0));
    for (int i=0; i<m; ++i) {
        for (int j=0; j<n; ++j) {
            if (matrix[i][j] == '1') {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    // 需要三个正方形均是
                    dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
                }
            }
            res = max(res, dp[i][j]);
        }
    }
    return res*res;
}

1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

解：这道题是算法导论中的例子，也是动态规划的经典题。需要注意状态变量的表示方法，用dp[i][j]表示text1以第 i 个字符结尾的子序列和text2以第 j 个字符结尾的子序列的公共子序列长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size();
    int n = text2.size();
    // dp[i][j]表示字符串1第i个字符结尾的字符串和字符串2第j个字符结尾的字符串的最长公共子序列
    vector<vector<int>> dp(m+1, vector(n+1, 0));
    for (int i=1; i<=m; ++i) {
        for(int j=1; j<=n; ++j) {
            if (text1[i-1] == text2[j-1]) {
                dp[i][j] = dp[i-1][j-1]+1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
}

背包问题

背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品 N，每个物品都有自己的重量 w 和价值 v ，在限定的总重量W内，我们如何选择，才能使得物品的总价值最高。如果限定每种物品只能选择 0 个或 1 个，则称为0-1背包问题，如何每种物品可以选择多次，则称为完全背包问题。

背包问题可以用动态规划来解决。

  1. 0-1 背包问题

定义一个二维数组dp[N+1][W+1],其中dp[i][j]表示前 i 件物品重量不超过 j 的情况下能装的最大价值。

对于第 i 件物品，设其价值为viv_i，重量为wiw_i，如果不选择，则有背包的最大价值：

dp[i][j]=dp[i−1][j]dp[i][j] = dp[i-1][j]

如果选择，则有背包的最大价值：

dp[i][j]=dp[i−1][j−wi]+vidp[i][j] = dp[i-1][j-w_i] + v_i

故状态转移方程为：

dp[i][j]=max(dp[i−1][j],dp[i−1][j−wi]+vi)dp[i][j] = max(dp[i-1][j], dp[i-1][j-w_i] + v_i)

程序为(该程序来自：https://github.com/changgyhub/leetcode_101)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int knapsack(vector<int> weights, vector<int> values, int N, int W) {
    vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= N; ++i) {
        int w = weights[i-1], v = values[i-1];
        for (int j = 1; j <= W; ++j) {
            if (j >= w) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[N][W];
}

实际上，可以看到状态转移方程中，dp[i][j]只和dp[i-1][j]以及dp[i-1][j-w]有关，所以实际上可以只用一个长度为 W 的数组重复利用以做到状态空间压缩。数组中后面的值依赖前面的值，为了保证数组元素更新时不覆盖掉还未使用的数，内层循环需要逆序。

1
2
3
4
5
6
7
8
9
10
int knapsack(vector<int> weights, vector<int> values, int N, int W) {
    vector<int> dp(W + 1, 0);
    for (int i = 1; i <= N; ++i) {
        int w = weights[i-1], v = values[i-1];
        for (int j = W; j >= w; --j) {
            dp[j] = max(dp[j], dp[j-w] + v);
        }
    }
    return dp[W];
}
  1. 完全背包问题

完全背包问题由于同一种物品可以重复选择多次，故对于第 i 件物品，设其价值为viv_i，重量为wiw_i，不选择时背包最大价值和 0-1背包问题一致，选择时有：

dp[i][j]=dp[i][j−wi]+vidp[i][j] = dp[i][j-w_i] + v_i

故状态转移方程为：

dp[i][j]=max(dp[i−1][j],dp[i][j−wi]+vi)dp[i][j] = max(dp[i-1][j], dp[i][j-w_i] + v_i)

不压缩空间时，程序和 0-1 背包问题类似，压缩空间时有所不同，现在状态转移方程中dp[i][j]和dp[i][j-w]有关，所以需要先算出第 j-w 列的值，才能算出后面的值，故内层循环是正向的。

1
2
3
4
5
6
7
8
9
10
int knapsack(vector<int> weights, vector<int> values, int N, int W) {
    vector<int> dp(W + 1, 0);
    for (int i = 1; i <= N; ++i) {
        int w = weights[i-1], v = values[i-1];
        for (int j = w; j <= W; ++j) {
            dp[j] = max(dp[j], dp[j-w] + v);
        }
    }
    return dp[W];
}

474. 一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中最多有m个0和n个1 。

1
2
3
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。

解：背包问题中只对物品总重量进行限制，这里对字符串中所含的0和1同时进行限制，所以需要增加一个维度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int findMaxForm(vector<string>& strs, int m, int n) {
    // 背包问题，多维
    int sz = strs.size();
    vector<vector<vector<int>>> dp(sz+1, vector<vector<int>>(m+1, vector<int>(n+1, 0)));
    for (int i=1; i<=sz; ++i) {
        const string& str = strs[i-1];
        int zero = 0, one = 0;
        for (char ch : str) {
            ch == '0' ? ++zero : ++one;
        }
        for (int j=0; j<=m; ++j) {
            for (int k=0; k<=n; ++k) {
                // 放不下当前的字符串
                if (j < zero || k < one) {
                    dp[i][j][k] = dp[i-1][j][k];
                } else {
                    dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-zero][k-one] + 1);
                }
            }
        }
    }
    return dp[sz][m][n];
}

为了节省空间，进行状态压缩：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int findMaxForm(vector<string>& strs, int m, int n) {
    // 背包问题，多维
    // 压缩空间
    int sz = strs.size();
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
    for (int i=1; i<=sz; ++i) {
        const string& str = strs[i-1];
        int zero = 0, one = 0;
        for (char ch : str) {
            ch == '0' ? ++zero : ++one;
        }
        // 为了重复利用数组，需要逆序遍历
        for (int j=m; j>=zero; --j) {
            for (int k=n; k>=one; --k) {
                dp[j][k] = max(dp[j][k], dp[j-zero][k-one] + 1);
            }
        }
    }
    return dp[m][n];
}

416. 分割等和子集

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

1
2
3
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

解：这道题换一种思路就是背包问题，问题等价于：在数组 nums 中选取若干个数，使得这些数的总和为所有数总和的一半。可以用dp[i][j]作为状态变量：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
bool canPartition(vector<int>& nums) {
    int sz = nums.size();
    int sum = 0, maxElem = 0;
    for (int& num : nums) {
        maxElem = max(maxElem, num);
        sum += num;
    }
    if (sum % 2) {
        return false;
    }
    int target = sum / 2;
    if (maxElem > target) {
        return false;
    }
    // 0-1背包问题
    // 从若干个数中选取部分数，它们的和是否能等于target
    // dp[i][j]表示从nums中前i个数中选取若干数之和能否等于target
    vector<vector<int>> dp(sz+1, vector<int>(target+1, 0));
    for (int i=0; i<=sz; ++i) {
        dp[i][0] = 1;
    }
    for (int i=1; i<=sz; ++i) {
        for (int j=1; j<=target; ++j) {
            if (nums[i-1] > j) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = dp[i-1][j - nums[i-1]] || dp[i-1][j];
            }
        }
    }
    return dp[sz][target];
}

压缩空间：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
bool canPartition(vector<int>& nums) {
    int sz = nums.size();
    int sum = 0, maxElem = 0;
    for (int& num : nums) {
        maxElem = max(maxElem, num);
        sum += num;
    }
    if (sum % 2) {
        return false;
    }
    int target = sum / 2;
    if (maxElem > target) {
        return false;
    }
    // 0-1背包问题
    // 从若干个数中选取部分数，它们的和是否能等于target
    vector<int> dp(target+1, 0);
    dp[0] = 1;
    for (int i=1; i<=sz; ++i) {
        for (int j=target; j>=nums[i-1]; --j) {
            dp[j] = dp[j-nums[i-1]] || dp[j];
        }
    }
    return dp[target];
}

实际上，这道题还有一个比较暴力的方法，就是想办法将数组nums的所有子集和计算并记录下来，然后判断是否有某个子集和等于总和的一半。可以通过集合进行操作，较好的方法是通过位域bitset来节省空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool canPartition(vector<int>& nums) {
    // 通过bitset来记录所有可能的子集和
    // 如bitset为 100110011001时，表示所有可能的子集和为1,3,4,7,8,11
    const int maxs = 20001;
    int sum = 0;
    static bitset<maxs> msk;
    msk.reset();
    // 第0位设置位为1
    msk.set(0);
    for(int x: nums) {
        // 向bitset中记录所有可能的子集和
        msk |= msk << x;
        sum += x;
    }
    // 判断第sum/2 位是否被设置为1
    return !(sum & 1) && msk.test(sum >> 1);
}

股票问题

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能在某一天买入，然后在未来某一天卖出，求能获得的最大利润。(只交易一次)

解：这道题是股票问题1，遍历数组，记住历史低价，然后不断计算当前的最大利润：

1
2
3
4
5
6
7
8
9
10
11
12
int maxProfit(vector<int>& prices) {
    // 历史最低价
    int min_price = prices[0];
    // 当前最大利润
    int profit = 0;
    for (int i=1; i<prices.size(); ++i) {
        min_price = min(min_price, prices[i]);
        profit = max(profit, prices[i] - min_price);
    }
    return profit;
}

122. 买卖股票的最佳时机 II

和上面一样，但是不限制交易次数。(你在任何时候 最多只能持有一股股票)

解：不限制交易次数的话，我们可以采用贪心策略，只要股票价格比昨天高，我们就卖出获得利润。

1
2
3
4
5
6
7
8
9
10
int maxProfit(vector<int>& prices) {
    int res = 0;
    for (int i=0; i<prices.size()-1; ++i) {
        if (prices[i] < prices[i+1]) {
            res += prices[i+1] - prices[i];
        }
    }
    return res;
}

123. 买卖股票的最佳时机 III

和上面一样，但是只能交易两次。

解：买卖股票问题，很多可以使用状态机来做，这里使用 4 组变量来表示 4 种状态：

  1. 当前持有第一支股票的最大利润buy1
  2. 当前卖出第一支股票的最大利润sell1
  3. 当前持有第二支股票的最大利润buy2
  4. 当前卖出第二支股票的最大利润sell2

弄清楚不同状态之间的转移关系就很好解决问题了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int maxProfit(vector<int>& prices) {
    int sz = prices.size();
    // 注意这里第 0 天还不能交易，必须将buy1[0]初始化为 小于等于 -prices[0]的数
    vector<int> buy1(sz+1, -prices[0]);  // buy1[i]表示第 i 天持有第一支股票的最大利润
    vector<int> sell1(sz+1, 0);
    vector<int> buy2(sz+1, -prices[0]);
    vector<int> sell2(sz+1, 0);
    for (int i=1; i<=sz; ++i) {
        // 遍历第 i 天至第 sz 天，当天可以做出 买/不买 或 卖/不卖 的选择
        buy1[i] = max(buy1[i-1], -prices[i-1]);
        sell1[i] = max(sell1[i-1], buy1[i-1] + prices[i-1]);
        buy2[i] = max(sell1[i-1] - prices[i-1], buy2[i-1]);
        sell2[i] = max(sell2[i-1], buy2[i-1] + prices[i-1]);
    }
    return sell2[sz];
}

通过上面的转移方程可以看出，每天的状态只和昨天的状态有关系，那么可以不需要使用数组来表示状态量，也就是可以进行状态压缩：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int maxProfit(vector<int>& prices) {
    int sz = prices.size();
    int buy1 = -prices[0], sell1 = 0;
    int buy2 = -prices[0], sell2 = 0;
    for (int i=1; i<=sz; ++i) {
        int n_buy1 = max(buy1, -prices[i-1]);
        int n_sell1 = max(sell1, buy1 + prices[i-1]);
        int n_buy2 = max(sell1 - prices[i-1], buy2);
        int n_sell2 = max(sell2, buy2 + prices[i-1]);
        buy1 = n_buy1;
        sell1 = n_sell1;
        buy2 = n_buy2;
        sell2 = n_sell2;
    }
    return sell2;
}

188. 买卖股票的最佳时机 IV

和上面一样，但是只能交易k次。

解：和「123. 买卖股票的最佳时机 III」类似，但是状态变量变多了，这里用二维数组表示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int maxProfit(int k, vector<int>& prices) {
    int days = prices.size();
    if (k > days) {
        // 相当于不限制交易次数
        return maxProfitNoLimit(prices);
    }
    // buy[i][j]表示第 i 天持有第 j 支股票时的最大利润
    // sell[i][j]表示第 i 天卖出第 j 支股票时的最大利润
    vector<vector<int>> buy(days+1, vector<int>(k+1, -prices[0]));  // 注意初始化
    vector<vector<int>> sell(days+1, vector<int>(k+1, 0));
    for (int i=1; i<=days; ++i) {
        for (int j=1; j<=k; ++j) {
            buy[i][j] = max(buy[i-1][j], sell[i-1][j-1] - prices[i-1]);
            sell[i][j] = max(buy[i-1][j] + prices[i-1], sell[i-1][j]);
        }
    }
    return sell[days][k];
}

int maxProfitNoLimit(vector<int>& prices) {
    int res = 0;
    for(int i=1; i<prices.size(); ++i) {
        if (prices[i] > prices[i-1])
            res += prices[i] - prices[i-1];
    }
    return res;
}

同样每天的状态只和昨天的有关，可以压缩空间到一维：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int maxProfit(int k, vector<int>& prices) {
    int days = prices.size();
    if (k > days) {
        // 相当于不限制交易次数
        return maxProfitNoLimit(prices);
    }
    vector<int> buy(k+1, -prices[0]);
    vector<int> sell(k+1, 0);
    for (int i=1; i<=days; ++i) {
        for (int j=1; j<=k; ++j) {
            buy[j] = max(buy[j], sell[j-1]-prices[i-1]);
            sell[j] = max(buy[j] + prices[i-1], sell[j]);
        }
    }
    return sell[k];
}

int maxProfitNoLimit(vector<int>& prices) {
    int res = 0;
    for(int i=1; i<prices.size(); ++i) {
        if (prices[i] > prices[i-1])
            res += prices[i] - prices[i-1];
    }
    return res;
}

309. 最佳买卖股票时机含冷冻期

和上面类似，但是卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

解：就不过多分析了，找清楚状态量和之间的转移关系，状态机轻松解决：

1
2
3
4
5
6
7
8
9
10
11
12
13
int maxProfit(vector<int>& prices) {
    int days = prices.size();
    vector<int> buy(days, 0);       // buy[i]:第i天持有股票的最大收益
    vector<int> sell(days, 0);      // sell[i]:第i天不持有股票且处于冷冻期的最大收益
    vector<int> sell2(days, 0);     // sell2[i]:第i天不持有股票且不处于冷冻期的最大收益
    buy[0] = -prices[0];
    for (int i=1; i<days; ++i) {
        buy[i] = max(buy[i-1], sell2[i-1] - prices[i]);
        sell[i] = buy[i-1] + prices[i];
        sell2[i] = max(sell2[i-1], sell[i-1]);
    }
    return max(sell[days-1], sell2[days-1]);
}

参考文献

  1. https://github.com/changgyhub/leetcode_101
  2. 《算法导论3th》