动态规划总结篇

1. 808 Soup Servings
2. 837 新21点
3. 464 can i win
4. 最大平均值和

1. 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];
    }

2. 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]

3. 464 can i win
   由于是无放回的抽取，所以不能使用动态规划。解法只能是带缓存的递归。

4. 813 最大平均值和的分组
   状态转移方程：dp[i][k] = max(dp[i][k], dp[j][k - 1] + 1.0 * (sum[i] - sum[j]) / (i - j))