一道似乎用DP也不能解决的题： diamond mine

dukemon7 发表于 2016-10-12 04:19
抱歉前两天没上地里，你就想成是去的时候走两条路，一直走到终点就好了，这样就不难想出来了

就是 开一个三维数组存两条路线各自能取得diamond的最大值 同时要求两个路线不能相交？[row][col1][col2]像这样？

33847682 发表于 2016-10-12 06:53
就是 开一个三维数组存两条路线各自能取得diamond的最大值 同时要求两个路线不能相交？[row][col1][col2] ...

存两条线一共能取到多少，所以最朴素的是四维，表示两条路走到哪两个点了，这时候的最大值，三维的表示法你需要再想想...你写的这个不行...另外不一定是不能相交，只是相交的时候只能记录一次

dukemon7 发表于 2016-10-12 08:34
存两条线一共能取到多少，所以最朴素的是四维，表示两条路走到哪两个点了，这时候的最大值，三维的表示法 ...

哦哦 我懂你的意思了 就是
dp[i1][j1][i2][j2]=max(dp[i1-1][j1][i2][j2],dp[i1][j1-1][i2][j2])+max(dp[i1][j1][i2-1][j2],dp[i1][j1][i2][j2-1]+val[i1][j1]+(i1==i2&&j1==j2)?0:val[i2][j2]
这样对嘛？

DP 可以解决的，经典的dp问题。去top coder看

mark下看看