- 808 Soup Servings
- 837 新21点
- 464 can i win
- 最大平均值和
- 808 Soup Servings
想到的方式是通过回溯暴力解，但是很明显不合理。
dp公式：f(a, b) = 0.25 * (f(a - 4, b) + f(a - 3, b - 1) + f(a - 1, b - 3) + f(a - 2, b - 2)
double memo[200][200];
double soupServings(int N) {
return N >= 4800 ? 1.0 : f((N + 24) / 25, (N + 24) / 25);
}
double f(int a, int b) {
if (a <= 0 && b <= 0) return 0.5;
if (a <= 0) return 1;
if (b <= 0) return 0;
if (memo[a][b] > 0) return memo[a][b];
memo[a][b] = 0.25 * (f(a-4,b)+f(a-3,b-1)+f(a-2,b-2)+f(a-1,b-3));
return memo[a][b];
}
- 837 新21点
想到的方法还是回溯递归，可以得到正确答案，但是时间复杂度会超。
dp公式：f(n)=f(n-1)/w + f(n-2)/w + ... + f(n-w)/w
#psuedocode
dp[k] = 1.0 when K <= k <= N, else 0.0
# dp[x] = the answer when Alice has x points
for k from K-1 to 0:
dp[k] = (dp[k+1] + ... + dp[k+W]) / W
return dp[0]
464 can i win
由于是无放回的抽取，所以不能使用动态规划。解法只能是带缓存的递归。813 最大平均值和的分组
状态转移方程：dp[i][k] = max(dp[i][k], dp[j][k - 1] + 1.0 * (sum[i] - sum[j]) / (i - j))
