目录
使用dp
python版本
java版本
递推式
python版本
java版本
PS:
java语法
1.定义数组
2.记忆化
3.计算max
难绷，本来想着4个指针，和四数之和那道题挺类似的。。。。
四数之和好像剪枝和预处理都是先排序的比较好做。
无奈，只能尝试先4层暴力再考虑优化。
4层暴力
class Solution:def maxScore(self, a: List[int], b: List[int]) -> int:m=len(b)mx=a[0]*b[0]+a[1]*b[1]+a[2]*b[2]+a[3]*b[3]#和四数之和的做法很类似啊,类似但貌似不会啊啊啊啊啊啊#逼我用4层暴力a1=0for a1 in range(m-3):b1=a1+1c1=a1+2d1=a1+3while d1<m:mx=max(mx,a[0]*b[a1]+a[1]*b[b1]+a[2]*b[c1]+a[3]*b[d1])d1+=1for a1 in range(m-3):b1=a1+1c1=a1+2while c1<m-1:d1=c1+1while d1<m:mx=max(mx,a[0]*b[a1]+a[1]*b[b1]+a[2]*b[c1]+a[3]*b[d1])d1+=1c1+=1for a1 in range(m-3):b1=a1+1while b1<m-2:c1=b1+1while c1<m-1:d1=c1+1while d1<m:mx=max(mx,a[0]*b[a1]+a[1]*b[b1]+a[2]*b[c1]+a[3]*b[d1])d1+=1c1+=1 b1+=1while a1<m-3:b1=a1+1while b1<m-2:c1=b1+1while c1<m-1:d1=c1+1while d1<m:mx=max(mx,a[0]*b[a1]+a[1]*b[b1]+a[2]*b[c1]+a[3]*b[d1])d1+=1c1+=1 b1+=1a1+=1return mx 显然超时
来个佬教我优化。
使用dp
从右往左求出的递推式
python版本
class Solution:def maxScore(self, a: List[int], b: List[int]) -> int:#缓存修饰器，避免重复计算dfs的结果@cachedef dfs(i,j):if j<0:return 0if i<0:return -infreturn max(dfs(i-1,j),dfs(i-1,j-1)+a[j]*b[i])return dfs(len(b)-1,3) 
java版本
class Solution {public long maxScore(int[] a, int[] b) {int n=b.length;long[][]memo=new long[n][4];for (long[]row:memo){//表示没有计算过Arrays.fill(row,Long.MIN_VALUE);}return dfs(n-1,3,a,b,memo);}private long dfs(int i,int j,int[] a,int[] b,long[][] memo){if (j<0){return 0;}if (i<0){//防止溢出return Long.MIN_VALUE/2;}//需要计算，并记忆化if (memo[i][j]==Long.MIN_VALUE){memo[i][j]=Math.max(dfs(i-1,j,a,b,memo),dfs(i-1,j-1,a,b,memo)+(long)a[j]*b[i]);}return memo[i][j];}
}
java真的快。
递推式
python版本
class Solution:def maxScore(self, a: List[int], b: List[int]) -> int:#递推式n=len(b)f=[[0]*5 for _ in range(n+1)]f[0][1:]=[-inf]*4for i,y in enumerate(b):for j,x in enumerate(a):f[i+1][j+1]=max(f[i][j+1],f[i][j]+x*y)return f[n][4]
java版本
class Solution {public long maxScore(int[] a, int[] b) {int n=b.length;long [][] f=new long[n+1][5];Arrays.fill(f[0],1,5,Long.MIN_VALUE/2);for (int i=0;i<n;i++){for (int j=0;j<4;j++){f[i+1][j+1]=Math.max(f[i][j+1],f[i][j]+(long)a[j]*b[i]);}}return f[n][4];}
} 
java非常快啊
PS:
java语法
1.定义数组
long[][]memo=new long[n][4];2.记忆化
for (long[] row : memo) {Arrays.fill(row, Long.MIN_VALUE); // 表示没有计算过}
3.计算max
Math.max()