Google电面面经

刚刚google电面面完，听说发到这里会有大米什么的？

就一个编程题，n个borad，两个颜色，相邻的三个board不能相同颜色，求一

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

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

。坐等大神现身，另外求个onsite，拿不到offer去蹭个饭也不错。

bless~~~

1. def f(n):
   
2.     if n==1: return 2;
   
3.     dp[2][0][1] = dp[2][0][0] = dp[2][1][0] = dp[2][1][2] = 1
   
4.     for i=3;i<=n;i++ {
   
5.       dp[i][0][1] = dp[i-1][1][0] + dp[i-1][0][0]
   
6.       dp[i][0][0] = dp[i-1][1][0]
   
7.       dp[i][1][0] = dp[i-1][0][1]+dp[i-1][1][1]
   
8.       dp[i][1][1] = dp[i-1][0][1]
   
9.     }
   
10.     return dp[n][0][0]+dp[n][0][1]+dp[n][1][0]+dp[n][1][1]

复制代码

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

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

是LC上Paint Fence这道题？

dp(i,x,y) 表示 前i个屋子已经涂了，第i个涂的颜色为y,第i-1涂的颜色为x的方法数。

这题简直是矩阵乘法的例题

1. A=[0,0,1,0;
   
2.       1,0,1,0;
   
3.       0,1,0,1;
   
4.       0,1,0,0]
   
5. if n==1: return 2;
   
6. else  return sum(A^(n-1))
   

复制代码

补充内容 (2015-10-21 08:04):
return sum(A^(n-2))

DP关系式应该是  res [ i ] = 2 * res [ i - 3 ] + res [ i - 1 ] 吧？

宝贝忆彼岸 发表于 2015-10-21 07:55
DP关系式应该是  res [ i ] = 2 * res [ i - 3 ] + res [ i - 1 ] 吧？

res [ i ] 表示前 i 个房子一共有多少种涂法

宝贝忆彼岸 发表于 2015-10-21 07:55
res [ i ] 表示前 i 个房子一共有多少种涂法

n=10的时候，结果是几？

应该是dp[i] = 2 x dp[i-1] - dp[i-3] 吧