Google 电面 2月份

Ethan248 发表于 2018-2-14 14:12
虽然知道要用dp，但题目都得看老半天。。。

电面一共45分钟，我光理解题意就花了差不多一半多的时间。

jjerry 发表于 2018-2-11 12:14
取一张牌之后，下次是从剩下9张里面取吗？还是每次取牌都有10种可能

每次都有10种可能

yyyang 发表于 2018-2-11 07:47
楼主，请问如果给的是15， 那么它busted的概率是什么啊。 dp[21 - 15] 吗？

dp[15] = 0.1 * dp[16] #抽到 1
          + 0.1*dp[17] # 抽到2
          + 0.1*dp[18] #抽到3
          + 0.1*dp[19] #抽到4
            .......

依次类推

anywho 发表于 2018-2-14 08:21
vector cal21(){
        vector res(27, 0);
        for(int i = 1; i

def cal21( num):
    dp = [1] * 100 #假设given number is less than 100.大于21的busted概率为1
    dp[17:22] = [0] * 6 # 17 - 21 之间busted概率是0
    dp[:17] = [0] * 17 # 小于17的数字初始化为0
     for i in range(16, num-1, -1): #一定要从16倒着来
        for j in range(10, 0, -1):
            dp[i] += dp[i+j] * 0.1
    return dp[num]



补充内容 (2018-2-15 12:22):
for 循环里是 dp[i] += dp[i+j] * 0.1

补充内容 (2018-2-15 12:23):
dp [ i ]  += dp[i+j] *0.1

liuzhe0320 发表于 2018-2-10 10:30
谢谢楼主的帖子，别灰心，结果还没出的，祝你找到早日找到工作！！！

谢谢安慰

Dp问题？这题是有些难度。。不过不一定非得完美才能拿offer，祝好运。

感谢分享，希望楼主一切顺利

加油楼主

这题很有意思啊

1. def cal21(num):
   
2.     dp=[1.0]*100
   
3.     dp[:22] = [0.0]*22  
   
4.     for i in range(16, num-1, -1):
   
5.       for j in range(10,0,-1):      
   
6.         dp[i]+=dp[i+j]*0.1
   
7.     return dp[num]
   
8. print(cal21(14))  

复制代码

initial: 0 - 21: 0.0 22 - 100: 1.0
16: dp[16]= (26-22)*0.1=0.5
15: dp[15]= (25-22)*0.1+(16)*0.1=0.4+0.5*0.1=0.45
14: dp[14]= (24-22)*0.1+(16)*0.1+(15)*0.1=0.3+0.05+0.045=0.395