Google 据信 ＋面经

bool f[k][i][j] is true if after k steps, we can end up at cell (i,j)

k is at most n^2

sailorconan 发表于 2014-11-13 23:27
要是两个方向还好，4个方向的dp？能写个递推公式吗？

bool f[k][i][j] is true if after k steps, we can end up at cell (i,j)

k is at most n^2

lz第二题印度小哥没让你做优化么，你写完了就完了？

lz第二题印度小哥没让你做优化么，你写完了就完了？

byrlhb 发表于 2014-11-14 01:24
lz第二题印度小哥没让你做优化么，你写完了就完了？

写完就没时间了，，，
第二题应该怎么做？

qiaokan 发表于 2014-11-13 23:31
bool f[k][j] is true if after k steps, we can end up at cell (i,j)

k is at most n^2

递推公式是？

我怎么觉得第二题和第一题是一样的。。无非加了两个方向。。

第二题用bfs 计算最长路径。。。 这样想比dp简单好多，就是不是那么efficient。。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

wondermu 发表于 2014-11-14 03:00
此题应该用dp的memoization,

here are the steps:

搜了一下， 这个的确算最佳解法 了。