leetcode 困难题 1458. Max Dot Product of Two Subsequences 两个子序列的最大点积

Problem: 1458. Max Dot Product of Two Subsequences 两个子序列的最大点积

动态规划的呢，dp[i][j]表示nums1的0-i-1前缀和nums2的0-j-1前缀的最大点积

初始化，最开始dp所有元素都是INT_MIN/10，考虑到子串非空，然后赋值的dp[1][1] = nums1[0] * nums2[0];

for(int i = 2; i <= n; i++) dp[i][1] = max(dp[i-1][1], nums1[i-1] * nums2[0]);，也就是考虑nums1[i-1]得到nums1[i-1] * nums2[0]，以及不考虑nums1[i-1]得到 dp[i-1][1]

for(int i = 2; i <= m; i++) dp[1][i] = max(dp[1][i-1], nums1[0] * nums2[i-1]);也就是考虑nums2[i-1]得到nums1[0] * nums2[i-1]，以及不考虑nums2[i-1]得到 dp[1][i-1]

递推公式是：

dp[i][j] = max({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+nums1[i-1]*nums2[j-1], dp[i-1][j-1], nums1[i-1]*nums2[j-1]});

也就是不考虑nums1[i-1]的dp[i-1][j]

不考虑nums2[j-1]的dp[i][j-1]

同时考虑nums1[i-1]和nums2[j-1]的dp[i-1][j-1]+nums1[i-1]*nums2[j-1]

同时不考虑nums1[i-1]和nums2[j-1]的dp[i-1][j-1]

不考虑 dp[i-1][j-1] 的 nums1[i-1]*nums2[j-1]

Code

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