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]Codeclass Solution { public: int maxDotProduct(vectorint nums1, vectorint nums2) { int n nums1.size(), mnums2.size(); vectorvectorint dp(n 1, vectorint(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]; } };