求解答，腾讯笔试，n*3的网格求最高得分

AC了，注意几个点 一是从后往前递归，而不是从前往后，初始状态是最后一行，赋初值 二是两个状态一个最小一个最大，如果是0就互相调换 这样可以过50 滚动优化后还是50，注意改为long long 就好了

这个魔法格子是翻转后面的不是翻转前面的，所以感觉dp不行啊，我用dp是50%

从后往前dp。。。变量注意用long，以后得先计算下变量的理想极限最大值，有两题都会因为这个被卡ac不能100

dp1[i][j]表示从当前位置（i,j）开始，且此时不存在取反操作时获得的最大积分，也就是进入（i,j）时没有取反这个命令，但之后可能遇到0而取反，但是这不关（i，j）的事，因为之后无论何时遇到0，都属于（i，j）位置不取反的情况，即使（i，j）为0也符合这种情况。 同理dp2[i][j]表示从（i，j）开始，此时存在取反操作。 #include <iostream> #include <vector> using namespace std; int main() {     int n;     int w[n][3];     for(int i=0;i<n;i++)         cin>>w[i][0]>>w[i][1]>>w[i][2];     int dp1[n][3], dp2[n][3];     memset(dp1, 0,sizeof(dp1));     memset(dp2, 0, sizeof(dp2));     for(int i=0;i<3;i++){         dp1[n-1][i]=w[n-1][i];         dp2[n-1][i]=-w[n-1][i];     }     for(int i=n-2;i>=0;i--){         for(int j=0;j<3;j++){             int h1 =INT_MIN, h2=INT_MIN;             for(k=max(0,j-1);k<=min(2,j+1);k++){                 if(w[i][j]){                     dp1[i][j] =max(h1, w[i][j]+dp1[i+1][k]);                     dp2[i][j] =max(h2, -w[i][j]+dp2[i+1][k]);                 }else{                     dp1[i][j] =max(h1, dp2[i+1][k]);                     dp2[i][j] =max(h2, dp1[i+1][k]);                 }             }         }     }     int res=INT_MIN;     for(int i=0;i<3;i++){         res=max(res,dp1[0][i]);     }     cout<<res; } 没测试哈~

初步测试以下递归算法可行： int score(int **a, int n, int m) { if (n < 0) { return 0; } if (m<0 || m>2) { return -INF; } int res = 0; int *s = new int[3]; for (int i = 0; i < 3; i++) { if (a[n][m] == 0) { s[i] = -score(a, n - 1, m + i - 1); } else { s[i] = a[n][m] + score(a, n - 1, m + i - 1); } } res = s[0]; for (int i = 0; i < 3; i++) { if (s[i]>res) { res = s[i]; } } return res; } 主函数： int main() { int n; cin >> n; int **a = new int*[n]; for (int i = 0; i < n; i++) { a[i] = new int[3]; for (int j = 0; j < 3; j++) { cin >> a[i][j]; } } int *res = new int[3]; for (int i = 0; i < 3; i++) { res[i] = score(a, n - 1, i); } int result = res[0]; for (int i = 0; i < 3; i++) { if (res[i]>result) { result = res[i]; } } cout << result << endl; system("pause"); return 0; }

动态规划有问题吧。。。。比如下一行都是负的这边选0大 但是后面出现了1000呢

我用了两个数组，一个存最大一个存最小，最后只有50。有ac的老哥吗