python - 在动态规划问题中得到错误答案或超出时间限制

Question

我正在尝试解决TRT Python3 的问题以及获取此代码的 WA:

from sys import stdin,stdout
try:

    def recur(a,l,r,cnt,ans, dp):
        # print(l,r,cnt,ans)
        if l>r:
            return ans
        if dp[l][r] !=-1:
            return dp[l][r]
        prev_ans=ans
        ans=max(ans, recur(a,l+1,r,cnt+1,prev_ans + cnt*a[l],dp))
        ans=max(ans, recur(a,l,r-1,cnt+1,prev_ans + cnt*a[r],dp))
        dp[l][r]=max(dp[l][r],ans)
        return ans

    n=int(stdin.readline())
    a=[]
    dp=[[-1 for x in range(n+5)] for z in range(n+5)]
    for i in range(n):
        a.append(int(stdin.readline()))

    stdout.write(str(recur(a,0,n-1,1,0,dp)))
except Excpetion as e:
    print(e)

根据评论中的一项建议，我尝试将 dp 数组长度更改为 2010，但后来我得到了 TLE。我尝试创建一个 TC，但失败了，但找不到任何东西，如果有人能给我建议，那就太好了。

Answer 1

以下代码在 C 语言中应用您的算法并被接受。

#include <stdio.h>
#include <stdlib.h>

#define max(a, b) (((a) > (b)) ? (a) : (b))

int f(int A[], int n, int l, int r, int dp[][2000]){
  int k = n - r + l;

  if (l == r)
    return A[l] * k;

  if (dp[l][r])
    return dp[l][r];

  return dp[l][r] = max(A[l] * k + f(A, n, l+1, r, dp), A[r] * k + 
 f(A, n, l, r-1, dp));
}

int main(void){
  int n;
  scanf("%d", &n);

  int A[n];
  int dp[2000][2000] = {0};

  for (int i=0; i<n; i++)
    scanf("%d", &A[i]);

  printf("%d", f(A, n, 0, n-1, dp));

  return 0;
}