如何将这个自上而下的dp转换为自下而上的dp

Question

给定两个大小为 n 和 m 的正整数数组 a 和 b，其中 n >= m，任务是通过在第二个数组中插入零来最大化点积，但不能扰乱元素的顺序。

大小为 n 的数组 a 和 b 的点积为 a[0]*b[0] + a[1]*b[1] + ... + a[n-1]*b[n-1]。

这是我写的解决方案，它工作得很好，但我无法想出迭代方法。

public int recurse(int a[], int b[],int aInd, int bInd, int zeroCount,int dp[][]){
        if(bInd>=b.length || aInd>=a.length)
            return 0;
            
       if(dp[aInd][bInd]!=-1)
         return dp[aInd][bInd];
           
       if(zeroCount==0){
            return dp[aInd][bInd]=a[aInd]*b[bInd]+recurse(a,b,aInd+1,bInd+1,0,dp);
        }
        
        
         int makeZero=recurse(a,b,aInd+1,bInd,zeroCount-1,dp);
         int noZero=a[aInd]*b[bInd]+recurse(a,b,aInd+1,bInd+1,zeroCount,dp);
           
         return dp[aInd][bInd]=Math.max(makeZero,noZero);
    }

Answer 1

令

dp[i][j]

表示使用数组

j

的前

b

元素与数组

i

的前

a

元素匹配时的最大可能点积。当

j < i

时，一些零被插入到

b

中。

转换是将

b

的当前元素与

a

的当前元素配对，在这种情况下，我们采用

dp[i - 1][j - 1]

加上两个相应元素的乘积，或者将

a

的当前元素相乘通过

0

，在这种情况下，我们只需尝试将

i - 1

的第一个

a

元素与

j

的第一个

b

元素（即

dp[i - 1][j]

）进行匹配。

那么实现就很简单了。

public int solve(int[] a, int[] b) {
    int[][] dp = new int[a.length + 1][b.length + 1];
    for (int i = 1; i <= a.length; i++)
        for (int j = 1; j <= Math.min(i, b.length); j++)
            dp[i][j] = Math.max(dp[i - 1][j - 1] + a[i - 1] * b[j - 1], dp[i - 1][j]);
    return dp[a.length][b.length];
}