Google Intern Interview加open offer

qeroqero 发表于 2016-11-21 13:37
dp是不能走回路的。如果水平上可以左右移，是没法dp的吧。比如［1，1］点既可以从［1，0］点到达，［1，0 ...

每一个点走法是上一行相应左右中三个点走法之和，就可以dp了，处始为左上点走法为1

楼主可不可以说下第一题的follow up 怎么做的？
第一个我是先从start 到 必须经过的点， 然后从这个点再到end， 不知道这样做对吗？  楼主怎么做的？

还有第二个follow up, 给一个set 的点，楼主怎么做的？

zhan1612 发表于 2016-11-22 11:58
楼主可不可以说下第一题的follow up 怎么做的？
第一个我是先从start 到 必须经过的点， 然后从这个点再到 ...

到每一行，看这一行有没有必须要经过的点，有的话只保留那个格的步数就可以了，其他都是0，没有就正常dp，有超过两个就直接return 0吧

问下楼主那个trie树预处理，需要code实现吗？还是说就行了？

tinyrookie 发表于 2016-11-22 17:14
问下楼主那个trie树预处理，需要code实现吗？还是说就行了？

时间不够了，说了说，画了一下示意图，怎么找start index和end index

哦哦，示意图是在doc里画吗。。。我以为doc里只能打码的。。

tinyrookie 发表于 2016-11-22 17:58
哦哦，示意图是在doc里画吗。。。我以为doc里只能打码的。。

就是空格换行，画一下简单的Trie示意图，然后说一下怎么从prefix的最后一个Trie Node出发找start index和end index. start index一直向最左走，直到遇到第一个index , end index一直向最右到尽头