谷歌

请问楼主第一题怎么做啊 感觉状态很多有速度 方向 位置坐标，实在想不出转移方程。。。。

iamafrican 发表于 2018-4-11 00:29
请问楼主第一题怎么做啊 感觉状态很多有速度 方向 位置坐标，实在想不出转移方程。。。。

dp解，dp[j]表示开到j处且保证方向超前的序列；
初始：
dp[1] = A
dp[2] = AARAR
递推如下：
对于len = p, 如果2^k-1 == p，dp[p] = k个A
否则，必有 2^k-1 < p < 2^(k+1) -1，要么先走k个A，转两次向，继续走p-2^k+1
要么走k+1个A，转一次向，走2^(k+1)-1-p，再转个向【保证到p时是超前的】



补充内容 (2018-4-12 17:17):
是朝前的，打错字了。
另外如果不允许连续两个R的话，那么第一种情况的转向需要变成RAR，相当于往回走了1步

alanlxl 发表于 2018-4-12 17:12
dp解，dp[j]表示开到j处且保证方向超前的序列；
初始：
dp[1] = A

大神，求最短序列的话，DP[2] = ARRA吧

alanlxl 发表于 2018-4-12 17:12
dp解，dp[j]表示开到j处且保证方向超前的序列；
初始：
dp[1] = A

另外像求教你一下长方形的走法那题：约束条件应该有一个格子不能重复走两遍，否则就是无限解了吧。那解的个数应该还是：dp[i][j] = dp[i-1][j] + dp[i][j-1] print path用个dfs function. dfs(grid, visited, si, sj, ti, tj) 这里需要判断一下如果si，sj四个方向全走遍了，那么si，sj不可能到达ti，tj的情况。

idatascience 发表于 2018-4-12 21:53
大神，求最短序列的话，DP[2] = ARRA吧

对，允许连续两个R的话
但我觉得这个题很可能就是限制不允许连续的R的，否则没任何难度啊；
不允许连续的R的情况下，dp[2] = AARAR

LC 竟然这么快就把这题收入了最新的contest 哈哈

补充内容 (2018-4-15 10:56):
第一题

补充内容 (2018-4-15 10:57):
818. Race Car

不知道是不是错觉 感觉第一轮巨难（也许是比较tricky，没见过这种题），后面的题目反而没那么难？

cow123311 发表于 2018-4-15 10:56
LC 竟然这么快就把这题收入了最新的contest 哈哈

补充内容 (2018-4-15 10:56):

楼主厉害！Leetcode新题好多跟面经一样的。

请问一下为啥要设置电脑？

多谢lz，看了LC 818，有点难度