1458. 兩個子序列的最大點積

思路

從左到右遍歷一遍陣列，看現在要「選或不選」看到的數字。

假如現在要選nums1[5]跟nums2[4]相乘，那麼有兩種答案可以考慮。

• 只選這兩個數字相乘：nums1[5] * nums2[4]。
• 這兩個數字之前還有數字要選：nums1[5] * nums2[4] + 前面得到的最佳結果。

這個「前面得到的最佳結果」，
就相當於把上面那整段內容的nums1[5]換成nums1[4]，nums2[4]換成nums2[3]。

定義dfs(i, j)代表「num1 前 i 個數字和 nums2 前 j 個數字所能得出的的最佳解答」。
此時dfs(i, j) = 以下選項取最大值

• dfs(i - 1, j)，最後一個數字沒配對。
• dfs(i, j - 1)，最後一個數字沒配對。
• dfs(i - 1, j - 1) + nums1[i] * nums2[j]，將nums1[i]跟nums2[j]配對，並接續前面的最佳解。
• nums1[i] * nums2[j]，不接續前面的最佳解。

1. dfs

class Solution {
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        vector<vector<int>> memo(n, vector<int>(m, INT_MAX));
        auto dfs = [&](this auto&& dfs, int i, int j) -> int {
            if(i < 0 || j < 0) return INT_MIN; // 不讓計算 MAX 時取到
            int& res = memo[i][j]; // 引用
            if(res != INT_MAX) {
                return res; // 已經計算過
            }
            res = max(dfs(i - 1, j - 1), 0) + nums1[i] * nums2[j];
            res = max(res, dfs(i - 1, j));
            res = max(res, dfs(i, j - 1));
            return res;
        };
        return dfs(n - 1, m - 1);
    }
};

複雜度分析

• 時間複雜度：$O(nm)$
• 空間複雜度：$O(nm)$

將遞迴轉換為動態規劃的形式，可以先將dp矩陣的第一行跟第一列初始化，再去做後續的計算， 或是將矩陣的範圍擴大一圈，減少程式法。 因為每次只會用到上一行的內容，可以將矩陣壓縮到一維。

2.動態規劃 (初始化)

class Solution {
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        vector<vector<int>> dp(n, vector<int>(m, INT_MIN / 2)); // / 2 避免溢出
        
        // 初始化 dp 陣列
        dp[0][0] = nums1[0] * nums2[0];
        for(int i = 1; i < n; ++i) {
            dp[i][0] = max(dp[i - 1][0], nums1[i] * nums2[0]);
        }
        for(int j = 1; j < m; ++j) {
            dp[0][j] = max(dp[0][j - 1], nums1[0] * nums2[j]);
        }

        for(int i = 1; i < n; ++i) {
            for(int j = 1; j < m; ++j) {
                int cur = nums1[i] * nums2[j];
                dp[i][j] = ranges::max({dp[i][j - 1], dp[i - 1][j], cur, dp[i - 1][j - 1] + nums1[i] * nums2[j]});
            }
        }
        return dp[n - 1][m - 1];
    }
};

3.動態規劃 (空間壓縮)

class Solution {
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        vector<int> lastDP(m + 1, INT_MIN / 2); // lastDP 可以改成單一變數，因為只用到 lastDP[j - 1] 這個固定位置。
        vector<int> dp(m + 1, INT_MIN / 2);
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= m; ++j) {
                int cur = nums1[i - 1] * nums2[j - 1];
                dp[j] = ranges::max({dp[j - 1], dp[j], cur, lastDP[j - 1] + cur});
            }
            lastDP = dp;
        }
        return dp.back();
    }
};

複雜度分析

• 時間複雜度：$O(nm)$
• 空間複雜度：壓縮前$O(nm)$，壓縮或$O(n)$