魔法师 (@Constanline) 在 Leetcode每日一题 —— 1458. 两个子序列的最大点积 中发帖
1458. 两个子序列的最大点积
思路
看题目应该是动态规划,转移方程也容易列出,
dp[i][j] = Max(dp[i - 1][j],dp[i][j - 1],dp[i - 1][x(= 0 .. j - 1)] + Max(nums1[i] * nums2[x .. j]),dp[x(= 0 .. i - 1)][j - 1] + Max(nums1[x .. i] * nums2[j - 1]))(后来发现我想复杂了)
代码
class Solution {
public int maxDotProduct(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int[][] dp = new int[m + 1][n + 1...