ひらめの日常

日常のメモをつらつらと

LeetCode: Max Dot Product of Two Subsequences (Hard)

問題はこちら

leetcode.com

二つの配列 nums1nums2 が与えられる。同じ長さの空でない部分列を nums1, nums2 から順序を変えずに選んだ時の内積の最大値を求めよ。

  •  1 \leq nums1.length, nums2.length \leq 500
  •  -1000 \leq nums1 _ {i} , nums2 _ {i} \leq 1000

考え方

DPの典型問題(解けませんでしたが... )

LCSと関わりが深いので、こちらの記事でLCSについて勉強しておくと良いかもしれない。

hiramekun.hatenablog.com

全ての部分列を考慮する方法だと、 \sum _ {i=1} ^ {500} {} _ {500} C _ {i} \times _ {500} C _ {i} 程度かかり到底間に合わない。

ここで注目したいのが、nums1[i1]nums2[i2] を使用した時、次に使用するのはそれぞれ i1, i2 以降のindexになるということだ。つまり、 「index(i1, i2) という状態は、それ以前のindexからしか到達しない」 ということ。

ここまでわかると、DPで解けることがわかる。というのも、題意をみたすように index i1, i2 の状態に来るには、なるべく大きい値を取るようにして遷移してくればよいためだ。

よって、DPの遷移は以下のようになる

  • dp[i1][i2]: nums1 i 番目、 nums2 j 番目 までの部分列における内積の最大値。
  • nums1[i1]nums2[i2] を使用する時
    • 題意では空でない部分列を求めるため、使用する場合は今までの値を使うか、それともこの場所から使用をスタートするかを選ぶことができる。
    • dp[i1][i2] = max(dp[i1][i2], max(0, dp[i1 - 1][i2 - 1]) + nums1[i1 - 1] * nums2[i2 - 1]
  • nums[i1]nums2[i2] を使用しない時
    • それぞれ、一つ隣のindexから遷移し、大きければ採用する。
    • dp[i1][i2] = max(dp[i1][i2 - 1], dp[i1][i2])
    • dp[i1][i2] = max(dp[i1 - 1][i2], dp[i1][i2])

解答

https://leetcode.com/submissions/detail/343972017/

class Solution {
public:
    int maxDotProduct(vector<int> &nums1, vector<int> &nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, INT_MIN));
        dp[0][0] = 0;
        for (int i1 = 1; i1 <= n1; ++i1) {
            for (int i2 = 1; i2 <= n2; ++i2) {
                dp[i1][i2] = max(dp[i1][i2 - 1], dp[i1][i2]);
                dp[i1][i2] = max(dp[i1 - 1][i2], dp[i1][i2]);
                dp[i1][i2] = max(dp[i1][i2],
                                 max(0, dp[i1 - 1][i2 - 1]) + nums1[i1 - 1] * nums2[i2 - 1]);
            }
        }
        return dp[n1][n2];
    }
};