问一道DP，真不会orz

Given a matrix of n*n.Each cell contain 0, 1, -1.
0 denotes there is no diamond but there is a path.
1 denotes there is diamond at that location with a path
-1 denotes that the path is blocked.

Now you have start from 0,0 and reach to last cell & then return back to 0,0 collecting maximum no of diamonds.
While going to last cell you can move only right and down. While returning back you can move only left and up.

Test case:

0 1 -1 1
1 0 -1 1
1 1 1 0
1 0 1 0

[size=0.8em]



补充内容 (2019-3-14 11:19):
左上角走到右下角，再走回左上角，钻石拿完了就没了不能重复拿

利口 柒肆壹 紫薯紫薯紫薯

从last cell回去不是原路返回就好了吗 假如来的时候是最优 那回去也是？向右向下不就对应向左向上吗？所以只需要考虑从左上角到右下角的最优解嘛？

我有理解错题目吗？

补充内容 (2019-3-14 11:22):
写完了才看到你的补充😂😂

那就等于解两次同一个问题/换个地图 因为有些位置钻石没了

补充内容 (2019-3-14 11:26):
我觉得可以 dp记录 到每个位置时可获得的最多钻石 然后记录前一步是来自左还是来自上 算完整个map之后 从终点backtrack回去更新地图 然后同样的 从右下角到左上角记录到每个位置时可获得的最多钻石 这次不用记前一步来自哪里

greatr22 发表于 2019-3-14 11:21
从last cell回去不是原路返回就好了吗 假如来的时候是最优 那回去也是？向右向下不就对应向左向上吗？所以 ...

我一开始也这么想的，但是不对，楼上leetcode有答案，我面DS遇见这种题我也是服气了orz

sunliwei 发表于 2019-3-14 11:31
我一开始也这么想的，但是不对，楼上leetcode有答案，我面DS遇见这种题我也是服气了orz

好像是不太合适呃。DS对算法是不是主要考核LC Medium的题，再加上DS特有的考核呢？

14417335 发表于 2019-3-14 21:23
好像是不太合适呃。DS对算法是不是主要考核LC Medium的题，再加上DS特有的考核呢？

据说一般是<= medium。主要一般考建模和统计。

741， youtube有个叫花花的哥们儿讲这个题讲的挺好的

sunliwei 发表于 2019-3-14 11:31
我一开始也这么想的，但是不对，楼上leetcode有答案，我面DS遇见这种题我也是服气了orz

这个题是真难，死活想不出。面试遇见这种认命吧

[p1_x, p1_y, p2_x, p2_y] dp
n^4的空间，时间。

优化为
[len, p1_x, p2_x] dp
n^3空间 时间。

这个是里口原题摘草莓