3836. Maximum Score Using Exactly K Pairs

You are given two integer arrays nums1 and nums2 of lengths n and m respectively, and an integer k.

You must choose exactly k pairs of indices (i_1, j_1), (i_2, j_2), ..., (i_k, j_k) such that:

• 0 <= i_1 < i_2 < ... < i_k < n
• 0 <= j_1 < j_2 < ... < j_k < m

For each chosen pair (i, j), you gain a score of nums1[i] * nums2[j].

The total score is the sum of the products of all selected pairs.

Return an integer representing the maximum achievable total score.

long long dp[111][111][111];
bool done[111][111][111];
class Solution {
    long long helper(vector<int>& A, vector<int>& B, int i, int j, int k) {
        if(done[i][j][k]) return dp[i][j][k];
        if(k == 0) return 0;
        done[i][j][k] = 1;
        int ra = A.size() - i, rb = B.size() - j;
        long long& res = dp[i][j][k] = helper(A,B,i+1,j+1,k-1) + 1ll * A[i] * B[j];
        if(ra > k) {
            res = max(res, helper(A,B,i+1,j,k));
        }
        if(rb > k) {
            res = max(res, helper(A,B,i,j+1,k));
        }
        return res;
    }
public:
    long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
        memset(done, 0, sizeof done);
        return helper(nums1, nums2, 0, 0, k);
    }
};