狗家跪经

祝福lz早日拿到合适的大大offer哦

补充内容 (2018-3-25 08:40):
想问问第三题是不是和这个题类似

http://www.techiedelight.com/fin ... e-node-descendants/

如果是分治法的话，难不成是bst?
那是不是又和这个题类似？

https://leetcode.com/problems/minim...

tinylic 发表于 2018-3-25 06:12
表示A还剩i毫升，B还剩j毫升的概率。
初始情况最后答案为sum

这样的做法相当于是枚举所有情况，一层一层地算下来，并不能通过cache 提高效率吧

n6134123 发表于 2018-3-25 04:49
想請問第四題cache思路是什麼+1，目前的想法是
Map
key = List =>  A剩餘數與B剩餘數的情況下

mem[i][j] 表示a中还剩i, b 中还剩j 时可以赢的概率。

double dfs(int a , int b) {
     if (a <= 0 && b > 0) return 1;
     if (a <= 0 && b <= 0) return 0;
     if (mem[a] != 0) return mem[a][b];
    double res = 1;
    res  = res * dfs(a - 100, b) * 0.25;
    res = res * dfs(a - 50, b - 50)*0.25;
     res = res * dfs(a - 75, b - 25)*0.25;
     res = res * dfs(a - 25, b - 75)*0.25;
    mem[a][b] = res;
    return res;
}

[b]补充内容 (2018-3-25 10:08):
mem[i][j]

补充内容 (2018-3-25 10:19):
最后return mem[5000][5000]

hululei 发表于 2018-3-25 09:59
这样的做法相当于是枚举所有情况，一层一层地算下来，并不能通过cache 提高效率吧

记忆化搜索就是动态规划啊┓( ′∀` )┏

tinylic 发表于 2018-3-25 10:11
记忆化搜索就是动态规划啊┓( ′∀` )┏

按照你的意思，dp[5000][5000] = 1;
dfs(double a,  double b, dp[][], double prev) {
    if (a <= 0 && b > 0) dp[a][b] += prev* 0.25;
    ...
   dp[a][b] += prev*0.25;
   dfs(a - 100, b, prev * 0.25);
   dfs(a - 50, b - 50, pre * 0.25);
   ....
}

你只是一层一层地计算到当前位置的概率是多少， 并不能重复利用之前的值。因为你的dp[][]里存的是到当前位置的概率，而不是在当前位置可以赢的概率。

hululei 发表于 2018-3-25 10:16
按照你的意思，dp[5000][5000] = 1;
dfs(double a,  double b, dp[][], double prev) {
    if (a  0)  ...

为什么要这样算呢？
f[i][j] = (f[i + 100][j] + f[i + 50][j + 50] + f[i + 75][j + 25] + f[i + 25][j + 75]) * 0.25

tinylic 发表于 2018-3-25 10:22
为什么要这样算呢？
f[j] = (f[j] + f[j + 50] + f[j + 25] + f[j + 75]) * 0.25

你不是说初始值f[5000][5000]= 1,
最后sum(f[0][1 : 5000])吗

tinylic 发表于 2018-3-25 10:22
为什么要这样算呢？
f[j] = (f[j] + f[j + 50] + f[j + 25] + f[j + 75]) * 0.25

那应该是
dp[0][0 : 5000] = 0;
dp[1: 5000][0] = 1;
dp[i][j] = (dp[i - 50][j - 50] + dp[i - 100][j] + dp[i - 75][j - 25] + dp[i - 25][j - 25]) * 0.25;

最后 return dp[5000][5000]

hululei 发表于 2018-3-25 10:46
那应该是
dp[0][0 : 5000] = 0;
dp[1: 5000][0] = 1;

dp[i+ 50][j + 50]打错了

hululei 发表于 2018-3-25 10:46
那应该是
dp[0][0 : 5000] = 0;
dp[1: 5000][0] = 1;

请问为啥 dp[1: 5000][0] 要initialize成1 ？