看到一题 求思路

- -这个难道不是刷题网骑士掉血那个题么

Black Liu 发表于 2020-8-28 04:48
反过来的话才比较好确定D和P吧，因为反过来的时候你可以去根据dp[j] and dp[j]然后套用
D和P看哪一个路 ...

没有很懂你的意思，不过记忆化递归和DP本质是可以相互转化，只是我个人感觉这题记忆化递归更容易理解吧。我的做法就是在每个位置，根据当前位置是D，P或num， 递归搜索右边和下边的子问题，然后取最小值。如果用reverse DP的话，感觉需要额外记忆两个dimension （D和P），因为如果是倒推，在某一点无法确定之前是否有D和P

二份答案然后dp一下咯？

你毛毛啊 发表于 2020-08-27 12:07:00
用记忆化递归写了然后test了一下应该是没问题，就是需要记忆多两个状态D和P。reverse DP感觉不是很好做啊，反过来的递推的时候没法确定是否之前有D和P，LZ有什么好的思路么？

dp reverse, 每个格子存三个数，假设前面没有D或P，假设前面有D，假设前面有P，最后推到左上角

War_Art 发表于 2020-08-27 03:43:36
感觉记忆化递归好一点吧，不然怎么确定后面哪个double哪个pass。或者先做一个预处理，把double向左向右所有能遇到方向上的正数乘2，double位置置0，pass同理？

reverse不用判断哪个double哪个pass，不用考虑路径了。如果从左上往右下找的话，路径不好判断

本来的思路是从左上往右下，写了几百行代码还不好判断double和pass。从右下往左上，不到50行就解决了🤦🏻‍♂️

glambertjay 发表于 2020-08-27 19:34:29
dp reverse, 每个格子存三个数，假设前面没有D或P，假设前面有D，假设前面有P，最后推到左上角

嗯 跟我想的reverse dp一样的，需要比正常多存两个维度，这么看来记忆化递归做这题可能更好？因为reverse dp有些情况应该是不存在的，正向递归的话就可以避免，我写的代码也是50行不到

你毛毛啊 发表于 2020-08-27 19:55:05
嗯 跟我想的reverse dp一样的，需要比正常多存两个维度，这么看来记忆化递归做这题可能更好？因为reverse dp有些情况应该是不存在的，正向递归的话就可以避免，我写的代码也是50行不到

正向递归碰到100*100或更多的的时间就太长了，不够效率

glambertjay 发表于 2020-08-27 20:06:36
正向递归碰到100*100或更多的的时间就太长了，不够效率

我说的是记忆化递归，所以每个位置只计算一次，应该是和dp一样。不过在这道题里，正向递归的话就不需要每个位置都考虑D和P

你毛毛啊 发表于 2020-08-27 20:11:27
我说的是记忆化递归，所以每个位置只计算一次，应该是和dp一样。不过在这道题里，正向递归的话就不需要每个位置都考虑D和P

那我帖子里提到的这个sample能跑出来吗？我觉得正向就必须考虑路径的选择。