求解答,腾讯笔试,n*3的网格求最高得分
看到这道题目的第一想法就是用动态规划来做,伪代码如下,求交流
大致思路是当前位置(i,j)处的最大值等于上一层能到达(i,j)处的值+(i,j)处值,在这些值中再求最大值。
int score(int **a, int i, int j) { if(i<0) { return 0; } if(j<0||j>2) { return -INF; } for(int i=0;i<3;i++) { if(a[i][j]==0) { s[i] = -score(a,i-1, j+i-1); } else { s[i] = a[i][j] + score(a, i-1, j+i-1); } } return max(s[0],s[1],s[2]); }