【415】【最高乘法得分】

目录

使用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()