Tìm tích vô hướng lớn nhất của hai mảng với chèn số 0 trong C++

Cho hai mảng số nguyên dương kích thước m và n (m > n). Cần tối đa hóa tích vô hướng bằng cách chèn số 0 vào mảng thứ hai, giữ nguyên thứ tự các phần tử. Ví dụ: A = [2, 3, 1, 7, 8], B = [3, 6, 7]. Kết quả tối đa là 107 bằng cách chèn 0 ở vị trí 1 và 3: 2×0 + 3×3 + 1×0 + 7×6 + 8×7 = 107.

Quy hoạch động

Tạo bảng DP kích thước (n+1)×(m+1) khởi tạo bằng 0. Công thức truy hồi:

dp[i][j] = max(dp[i-1][j-1] + A[j-1]*B[i-1], dp[i][j-1])

Ví dụ minh họa

#include <iostream>
using namespace std;

long long findMaximumDotProd(int A[], int B[], int m, int n) {
    long long dp[100][100] = {0};
    
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= m; j++)
            dp[i][j] = max(dp[i-1][j-1] + 1LL*A[j-1]*B[i-1], dp[i][j-1]);
    
    return dp[n][m];
}

int main() {
    int A[] = {2, 3, 1, 7, 8};
    int B[] = {3, 6, 7};
    int m = sizeof(A)/sizeof(A[0]);
    int n = sizeof(B)/sizeof(B[0]);
    cout << "Tích vô hướng lớn nhất: " << findMaximumDotProd(A, B, m, n);
    return 0;
}

Kết quả

Tích vô hướng lớn nhất: 107