twitter sde 电面~~~

zhiyiting 发表于 2015-2-26 02:14
肥霸面吃豆子

补充内容 (2015-2-26 06:21):

这是1d还是2d dp么？ 能详细讲下？

zhiyiting 发表于 2015-2-26 02:14
肥霸面吃豆子

补充内容 (2015-2-26 06:21):

你这是一维DP,  P【j】定义的是啥？

tyr034 发表于 2015-3-3 10:46
楼主能不能分享下思路啊

我当时也挂了。。。弄个二维DP P[W][R]

肥霸 发表于 2015-3-3 12:46
你这是一维DP,  P【j】定义的是啥？

我这是二维DP，系统把我的[ i ]当成italic吃掉了
肥霸求光环啊，我也要面试了～～当年拿了你的托福书就考得很好。。

douya 发表于 2015-3-3 12:28
这是1d还是2d dp么？ 能详细讲下？

Pi,j = j/(i+j)*Pi,j-1 + i/(i+j)*(i/(i+j) * Pi-1,j + j/(i+j)*Pi,j-1)
当前这一轮，有i个红色豆子，j个白色豆子
如果拿了白色豆子，就吃掉，所以最后一轮是白色豆子就是i红豆j-1白豆概率，两件事情同时发生，j/(i+j)*Pi,j-1
如果拿到红色豆子，就放回去，再拿一个吃掉，如果再拿到红色豆子，就是i-1,j豆子概率，如果再拿到白色豆子，就是i,j-1概率
不知道对不对。。

zhiyiting 发表于 2015-3-3 12:59
Pi,j = j/(i+j)*Pi,j-1 + i/(i+j)*(i/(i+j) * Pi-1,j + j/(i+j)*Pi,j-1)
当前这一轮，有i个红色豆子，j ...

算了一下，是不对的

zhiyiting 发表于 2015-3-3 12:49
我这是二维DP，系统把我的[ i ]当成italic吃掉了
肥霸求光环啊，我也要面试了～～当年拿了你的托福书就 ...

同求光环~~~~~~~~~~~~那感觉你做的差不多了，就是要么吃掉一个白球，要么吃掉一个红球，所以P[R][W] = P[R-1][W] *ＸＸ　＋　P[R][W－１] *ＸＸ
ＸＸ是一些转移概率

你的系数还有一些问题估计，如果错了的话

zhiyiting 发表于 2015-3-3 13:44
算了一下，是不对的

我感觉是这样：换个定义方法，pi,j不是吃了i+j个，而是还剩i red, j white。
pi,j = pi+1,j *(i+1)/(i+1+j) * (i+1)/(i+1+j)
      + pi,j+1 * (（j+1)/(i+1+j) + (1-（j+1)/(i+1+j))*（j+1)/(i+1+j) )

最后求的是p0,1

楼上貌似不太对~~~最好反过来想