[LeetCode]1458. Max Dot Product of Two Subsequences

https://leetcode.com/problems/max-dot-product-of-two-subsequences/description/

LeetCode - The World's Leading Online Programming Learning Platform

문제 유형 : 다이나믹 프로그래밍

문제 난이도 : Hard

 

문제

Given two arrays nums1 and nums2.

Return the maximum dot product between non-empty subsequences of nums1 and nums2 with the same length.

A subsequence of a array is a new array which is formed from the original array by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, [2,3,5] is a subsequence of [1,2,3,4,5] while [1,5,3] is not).

 

두 배열 nums1과 nums2가 주어진다. 같은 크기의 서브시퀀스(요소의 일부만 빼온)의 각 요소들의 곱의 합의 최대값을 구하시오.

순서가 바뀌어서는 안 됩니다.

 

풀이

최대 값을 가지는 dp테이블을 만든다.

dp[i][j]는 이전 값(dp[i-1][j-1])에다가 nums[i] * nums[j]를 곱한 값과, dp[i-1][j], dp[i][j-1]의 값들 중 최대값으로 갱신시킨다.

 

코드

C++

class Solution {
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);

        const int n = nums1.size();
        const int m = nums2.size();

        vector<vector<int>> dp(n+1, vector<int>(m+1, INT_MIN));

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

        return dp[n][m];
    }
};