讨论/《高频算法实战》 - 动态规划理论/
《高频算法实战》 - 动态规划理论
共 8 个回复

讲的特别好啊 学到了

1

1

666

dddddddddddd

请问,[x][y]表示的是,前x枚中y枚朝上的情况吗?

我们的思路好像不太一样,我以为的是[i][j]表示当前,[x][y]表示上次

1、[i][j]的概率由两个不同的上上次结果相加
p[i][j]=p[i][j][i-1][j-1]+p[i][j][i-1][j];
2、
p[i][j][x][y]=p[x][y][x-1][y-1]*0.5 + p[x][y][x-1][y];

不知道有没有错

"那么对应的,dp[i][j] 状态我们可能从 dp[i-1][j]和dp[i-1][j-1] 转移过来。分别代表第i件物品是拿还是不拿。"
反了吧

自底向上的动态规划,请各位路过的大佬看一下有没有问题

# f(i, j, x, y) 表示丢i枚硬币,j枚朝上的概率,其中,x表示上上次投的情况,y表示上次投的情况
if x == y and x == 1:
	# 前两枚都朝上,那么第i+1枚必须朝下
	f(i + 1, j, y, 0) += f(i, j, x, y)
elif x == y and x == 0:
	# 前两枚都朝下,那么第i+1枚必须朝上
	f(i + 1, j + 1, y, 1) += f(i, j, x, y)
else:
	# 第i+1枚朝下
	f(i + 1, j, y, 0) += f(i, j, x, y) * 0.5
	# 第i+1枚朝上
	f(i + 1, j + 1, y, 1) += f(i, j, x, y) * 0.5