本次作业将力扣多维动态规划题目全部完成。

力扣 面试经典 150 题 - 多维动态规划

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

思路

令 $dp[i][j][k]$ 表示第 $i$ 天，已经进行了 $j$ 次交易，且当前持有股票状态为 $k$（$k=0/1$ 表示不持有/持有）时的最大收益。因此动态转移方程为：$dp[i][j][0] = \max({dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]}), dp[i][j][1] = \max({dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]})$。因为每个位置只会被更新一次，因此算法复杂度为 $\mathrm O(n)$。
在实际编码中，我们发现 $dp[i][j][k]$ 的更新只会用到 $dp[i - 1][?][?]$，与之前的状态无关，因此可以将第一维的空间省略，以减小空间复杂度。

代码

提交记录：100ms (94.58%) / 72.00MB (77.41%)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int dp[2][2]; // 买入量，是否持有股票
        memset(dp, -0x7f, sizeof(dp));
        for (int i = 0, ed = prices.size(), p = prices[0]; i < ed; ++i, p = prices[i]) 
            dp[0][0] = max(dp[0][0], dp[1][1] + p), dp[1][1] = max(dp[1][1], dp[1][0] - p),
            dp[1][0] = max(dp[1][0], dp[0][1] + p), dp[0][1] = max(dp[0][1], -p);
        return max(0, max(dp[0][0], dp[1][0]));
    }
};

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

思路

递推公式同上题，同样可以压掉一维，复杂度 $\mathrm O(n\times k)$。

代码

提交记录：4ms (97.54%) / 10.61MB (84.08%)

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int dp[101][2], ans = 0; // 买入量，是否持有股票
        memset(dp, -0x7f, sizeof(dp));
        for (int i = dp[0][0] = 0, ed = prices.size(), p = prices[0]; dp[0][1] = max(dp[0][1], -p), i < ed; ++i, p = prices[i < ed? i : 0])
            for (int j = k; j > 0; --j) dp[j][1] = max(dp[j][1], dp[j][0] - p), ans = max(ans, dp[j][0] = max(dp[j][0], dp[j - 1][1] + p));
        return max(0, ans);
    }
};

LeetCode 221. 最大正方形

思路

令 $dp[i][j]$ 表示以 $(i, j)$ 为右下角的最大正方形的边长。因此动态转移方程为：$dp[i][j] = \min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1$，即当左上、左边、上边一格都为对应大小的正方形时当前格子才能形成正方形，且不会更大。因为每个位置只会被更新一次，因此算法复杂度为 $\mathrm O(n^2)$。

在实际代码实现上，由于每次更新只会用到上一行的数据，因此可以通过滚动数组的形式将空间复杂度降低到 $\mathrm O(n)$。

代码

提交记录：60ms (98.55%) / 17.96MB (96.95%)

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int ans = 0, dp[2][305];
        for (int i = 0, n = matrix.size(), m = matrix[0].size(); i < n; ++i)
            for (int j = 0; j < m; ++j)
                ans = max(ans, dp[i & 1][j] = matrix[i][j] & 1 ? min(i ? dp[i + 1 & 1][j] : 0, min(j ? dp[i & 1][j - 1] : 0, i && j ? dp[i + 1 & 1][j - 1] : 0)) + 1 : 0);
        return ans * ans;
    }
};

力扣 面试经典 150 题 - 数组 / 字符串

LeetCode 88. 合并两个有序数组

思路

倒序将数字复制进 $nums1$ 即可。

代码

提交记录：0ms (100.00%) / 9.04MB (13.51%)

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for (int i = m + n - 1; i > -1; --i)
            nums1[i] = (m ? nums1[m - 1] : -2e9) > (n ? nums2[n - 1] : -2e9) ? nums1[--m] : nums2[--n];
    }
};

LeetCode 27. 移除元素

思路

倒序将数字复制进 $nums1$ 即可。

代码

提交记录：0ms (100.00%) / 9.04MB (13.51%)

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for (int i = m + n - 1; i > -1; --i)
            nums1[i] = (m ? nums1[m - 1] : -2e9) > (n ? nums2[n - 1] : -2e9) ? nums1[--m] : nums2[--n];
    }
};