描述

给定长度为 N 的 A 数组，长度为 K 的 B 数组

你可以从 A 数组里取 K 个数

规则如下：

• 每个 Ai 只能被取出一次
• i==1ori==N 可以直接取出 Ai
• 2≤i≤N−1 若 Ai−1 或者 Ai+1 已经取出，则可以取出 Ai
• 要取出正好 K 个数

即每次可以从 A 数组的最左边或者最右边取走一个数，取走的数从数组中移除 将取出的 Ai 按取出的顺序 组成 C 数组 求 B 与 C 的内积最大值

B 与 C 内积为∑i=0K−1Bi×Ci 解释 1： A= [1,4,3,2,5] B=[1,2,3,4] K=4 取出 A0 ,C=[1] 取出 A4 C=[1,5] 取出 A1 C=[1,5,4] 取出 A2 C=[1,5,4,3] B·C=11+25+34+43=35 这只是 C 的一种可行方案，可能不是最优方案 解释 2 A=[1,2,3,4] 不能直接取出 A1 因为 A0 和 A2 都没有取出

1≤K≤N≤2000 1≤Ai,Bi≤100000

在线评测地址

样例

[2,3,5,1] [2,1] 取出 A0,A1 

算法 DP

1. DP 方程 dpijdpij 表示从左边取了 i 个数，从右边取了 j 个数的最大内积
2. DP 方程转移

即判断上一次从左边取还是从右边取数哪个内积更大 3. DP 边界条件 dp00=0dp00=0 两边都没取数 内积为 0 4. 答案 ans=max(ans,dpiK−i)ans=max(ans,dpiK−i) 即枚举左边取了多少个数，答案取 dp 数组最大值

复杂度分析

• 时间复杂度 n 是 A 数组长度 K 是 B 数组长度 左右两边取数均不超过 K 个 所以状态量 O(K2)O(K2) 转移 O(1)O(1) 所以总时间复杂度 O(K2)O(K2)
• 空间复杂度 左右两边取数均不超过 K 个 所以状态量 O(K2)O(K2) 所以总空间复杂度 O(K2)

public class Solution {     /**      * @param A: the A array      * @param B: the B array      * @return: return the maxium inner product of B and C      */     public long getMaxInnerProduct(int[] A, int[] B) {         // write your code here         //A 数组长度         int  n = A.length;         //B 数组长度         int  K = B.length;         //初始化 dp 数组         //dp[i][j]表示从左边取了 i 个数，从右边取了 j 个数的最大内积         long [][]dp = new long [K + 1][K + 1];          //枚举 dp[i][j]         for(int i = 0; i <= K; i++) {             for(int j = 0; j <= K; j++) {                  //从左边和右边取数总数不超过 K 个                 if(i + j > K) {                     break;                 }                 if(i + j > n) {                     break;                 }                 //dp 数组边界条件，从左右都不取数的时候，dp[0][0]=0                 if(i == 0 && j == 0) {                     dp[i][j] = 0;                     continue;                 }                  //从左边取的 i 更新 dp[i][j]                 if(i != 0) {                     dp[i][j] = Math.max(dp[i][j], dp[i - 1][j] + (long)A[i - 1] * (long)B[i + j - 1]);                 }                 //从右边取的 j，更新 dp[i][j]                 if(j != 0) {                     dp[i][j] = Math.max(dp[i][j], dp[i][j - 1] + (long)A[n - j] * (long)B[i + j - 1]);                 }              }         }         //枚举从左边取了多少，找最大的内积         long ans = 0;         for(int i = 0; i <= K; i++) {             ans = Math.max(ans, dp[i][K - i]);         }                  return ans;     } } 

更多题解参考

大佬有話說 (0)