1458. Max Dot Product of Two Subsequences

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).

class Solution {
    vector<vector<int>> dp;
    int helper(vector<int>& nums1, vector<int>& nums2, int i, int j) {
        if(i == nums1.size() or j == nums2.size()) return INT_MIN;
        if(dp[i][j] != INT_MIN) return dp[i][j];
        dp[i][j] = max({
            helper(nums1, nums2, i + 1, j),
            helper(nums1, nums2, i, j + 1),
            max(helper(nums1, nums2, i + 1, j + 1),0) + nums1[i]*nums2[j]
            });
        return dp[i][j];
    }
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        dp = vector<vector<int>>(nums1.size() + 1, vector<int>(nums2.size() + 1, INT_MIN));
        return helper(nums1, nums2, 0, 0);
    }
};