algorithm - 如何将以下递归转换为自上而下的动态规划？

Question

我正在尝试解决 Maximum Product Subarray来自 leetcode 的问题。

问题描述是:给定一个整数数组，找到数组中至少包含一个数且乘积最大的连续子数组。

示例:输入:[2,3,-2,4]，输出:6

为了解决这个问题，我使用了以下逻辑:让 f(p,n) 输出正确的结果，直到结果为 p 的数组的索引 n 为止。所以递归是:

f(p,n) = p // if(n=a.length)
f(p,n) = max( p, f(p*a[n], n+1), f(a[n], n+1) ) // otherwise

这适用于常规递归(下面的代码)。

private int f(int[] a, int p, int n) {
    if(n==a.length)
        return p;
    else
        return max(p, f(a, p*a[n], n+1), f(a, a[n], n+1));
}

但是我无法将其转换为自上而下的动态规划。我一直用来将递归程序转换为使用自上而下 DP 的方法是:

• 初始化缓存(我将使用数组)
• 如果索引 'n' 处的缓存已被填充，则返回该值作为结果
• 否则递归并将结果存储在缓存中
  • 从缓存中返回值。

这是我一直在使用的一种通用方法，它适用于我做过的大多数 dp 问题，但不适用于这个问题。

使用这种方法的(不正确的)代码如下所示:

private int f(int[] a, int p, int n, int[] dp) {
    if(dp[n]!=0)
        return dp[n];
    if(n==a.length)
        dp[n] = p;
    else
        dp[n] = max(p, f_m(a, p*a[n], n+1, dp), f_m(a, a[n], n+1, dp));
    return dp[n];
}

我从主函数调用函数如下:

// int x = f(a, a[0], 1, dp); - for incorrect top-down dp attempt
// int x = f(a, a[0], 1); - for regular recursion

它不起作用的一个例子是:[3,-1,4]。这里它错误地输出了 3 而不是 4。

据我了解，问题是因为两个子问题都引用了 DP 数组的同一个 n+1 索引，所以只解决了 1 个子问题，这导致了错误的答案。

所以我的问题是:

如何将这个循环转换为自上而下的 DP 程序？对于这种情况，是否有我可以遵循的通用方法？

Answer 1

您的dp 状态取决于当前索引n 和当前结果p。因此，您需要将结果存储在 2D 数组中，而不是仅使用 1D 数组作为索引。

private int f(int[] a, int p, int n, int[] dp) {
    if(dp[n][p]!=0)
        return dp[n][p];
    if(n==a.length)
        dp[n][p] = p;
    else
        dp[n][p] = max(p, f_m(a, p*a[n], n+1, dp), f_m(a, a[n], n+1, dp));
    return dp[n][p];
}