狗家跪经

yuxrose

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

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

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

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

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

l553585

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

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

l553585

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

tinylic

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

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

l553585

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

tinylic

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

l553585

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])吗

l553585

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

l553585

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

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

wtcupup

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

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