求助一个google的高频电面题目!

SimonLevy 发表于 2019-10-5 06:20
提供个思路，用dp，dp** 表示endwith**，长度为i的string的数量，例如dp00 就是endwith 00，并且长度为i

...

然后把这个凑一下就是dp[i] = dp[i - 1] + dp[i - 2]

我也提供一个思路吧，就算数的

dp的话就是 dp[n] = 2*dp[n-1] - dp[n-3]

可能比较容易理解一点，就是把所有长度为n-1的符合条件的str后面加0或者加1，会得到2*dp[n-1]这么多的str，但是里面有一些是不符合条件的，就把它们减掉，这些不符合条件的str出现三个连续的0或1的地方只会在最后三位，一半是000，另一半是111，一共有dp[n-3]这么多个

算出来的结果和dp[n] = dp[n-1] + dp[n-2]是一样的

写成代码是
def dp(n):
    if n == 0:
        return 1
    elif n == 1:
        return 2
    elif n == 2:
        return 4
    elif n == 3:
        return 6
    else:
        return 2*dp(n-1) - dp(n-3)

yiliaobailiao 发表于 2019-10-5 08:12
实在不敢当。没想通，所以想问一下，为什么要加这个check呢？按理说，不会有>n的情况出现的吧。不过我确 ...

看你说的，我又回去重新run了一下。的确是不需要。奇怪，我上次run的时候 stackover flow了，加了以后好了。Anyway，纠正一下，的确是不需要的，😅

vanpyz2019 发表于 2019-10-5 08:22
DP:
F[n] = F[n-1] + F[n-2]
F[1] = 2

赞 👍

tianyug 发表于 2019-10-6 10:36
我也提供一个思路吧，就算数的

dp的话就是 dp[n] = 2*dp[n-1] - dp[n-3]

赞 👍