1458. Max Dot Product of Two Subsequences

• Hint를 보고 푼 문제 (DP를 쓰자). Memoize를 할 때 각 nums1, nums2 array에서 몇번째 index 부터 element를 골라 dot product를 계산할지 기록하면 된다.

• 점화식
• nums1, nums2의 길이를 각각 M, N 이라고 할 때
• 각각 M - 1, N - 1 부터 element를 고르게 되면 마지막 element의 dot product가 된다.
• dp[M - 1][N - 1] = nums1[M - 1] * nums2[N - 1]
• 이를 기반으로 아래 두 가지 경우의 값을 계산한다
• nums1에서 각 index 별 element * nums2의 마지막 element
• dp[i][N - 1] = max(dp[i + 1][N - 1], nums1[i] * nums[N - 1])
• nums1에서 마지막 element * nums2에서 각 index 별 element
• dp[M - 1][j] = max(dp[M - 1][j + 1], nums1[M - 1] * nums[j])

• 계산 과정
• 계산 과정에서는 (M - 2 ~ 0, N - 2 ~ 0) 범위에 대해서 역순으로 값을 계산해나간다.
• 계산시에는 다음의 4가지 경우를 고려하여 가장 큰 값을 취한다.
• (1) 현재 index의 element 간 dot product
• nums1[i] * nums2[j]
• 현재 index 보다 큰 범위의 값을 다 무시하는 경우에 해당된다.
• (2) (i + 1 ~ M - 1, j + 1 ~ N - 1) 범위의 값 + (1) 번의 값
• dp[i + 1][j + 1] + nums1[i] * nums2[j]
• 현재 index보다 큰 범위의 값 + 현재 index의 dot product로 계산하는 경우
• (3) (i + 1 ~ M - 1, j ~ N - 1) 범위의 값
• dp[i + 1][j]
• nums1의 현재 index i의 값을 무시
• (4) (i ~ M - 1, j + 1 ~ N - 1) 범위의 값
• dp[i][j + 1]
• nums2의 현재 index j의 값을 무시

• 결과값
• 결국 전체 index인 (0 ~ M - 1, 0 ~ N - 1) 범위의 dot product max 값을 구해야 하므로 dp[0][0]의 값을 결과로 돌려주면 된다.

class Solution {
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(500, vector<int>(500, INT_MIN));
        int M = nums1.size();
        int N = nums2.size();
        dp[M - 1][N - 1] = nums1[M - 1] * nums2[N - 1];
        for (int i = M - 2; i >= 0; --i) {
            dp[i][N - 1] = max(
                dp[i + 1][N - 1], 
                nums1[i] * nums2[N - 1]
            );
        }
        for (int j = N - 2; j >= 0; --j) {
            dp[M - 1][j] = max(
                dp[M - 1][j + 1], 
                nums1[M - 1] * nums2[j]
            );
        }

        for (int i = M - 2; i >= 0; --i) {
            for (int j = N - 2; j >= 0; --j) {
                int product = nums1[i] * nums2[j];
                int value = product;
                value = max(value, dp[i + 1][j + 1] + product);
                value = max(value, dp[i + 1][j]);
                value = max(value, dp[i][j + 1]);
                dp[i][j] = value;
            }
        }
        return dp[0][0];
    }
};