新21点

发表于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

LeetCode每日一题，837.House Robber

先看题目描述

题目大意是爱丽丝玩个游戏，游戏规则是这样：

  1. 她可以从牌面为[1,W]的牌中选择任意一张，这张牌是可以无限重复的，也就是说无论她取多少次，每次取到2（假如2在[1,W]范围内）的概率都是 1/W
  2. 如果她手上牌的总额小于 K，她就会抽牌，大于等于 K 时，就停止抽牌
  3. 停止抽牌后，她的牌面小于等于 N 时，她就获胜了，求她获胜的概率

这道题一直没有头绪，也有往动态规划那方面想，但一直想不到，后来看了题解才把代码实现，但觉得自己做的话是想不到那个动态规划方程的

算法和思路

假设 dp[x] 表示她手上牌面为 x 时，能获胜的概率，那么这个概率应该是：
dp[x] = 1/w * (dp[x+1]+dp[x+2]+dp[x+3]…+dp[x+w])
因为抽取的牌面机会都是均等的，她能抽取的面值在 [1,W] 之间，所以将概率之和平均一下就是 dp[x] 的概率。
x 最多能到 K-1，因为当大于等于 K 时，爱丽丝会停止抽牌，所以当游戏结束时，即爱丽丝停止抽牌时，她可能达到的最大牌面是 K+W-1 ，而一开始她的牌面是 0，所以我们用一个长度为 K+W 的 dp 数组来保存她在所有面值下的胜率。
最后返回 dp[0]，也就是最开始爱丽丝还没有抽牌，她的牌面为 0 时的胜率，这个就是我们的答案

dp 数组可以分为两部分，当下标 i 大于等于 K 时，因为此时不能抽牌，则只需将 i 与 N 比较，若 i <= N，则 dp[i] = 1，否则 dp[i] = 0，当下标 i 小于 K 时，就利用上面的动态规划方程来计算 dp[i]，而为了避免时间超出限制，我们不能每次计算时都累加，可以定义一个变量 s 保存累加结果，计算下一轮时只需减去右边的，加上左边的，更新 s 即可

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public double new21Game(int N, int K, int W) {
        double[] dp = new double[K + W];
        double s = 0;
        for (int i = K + W - 1; i >= K; i--) {
            dp[i] = i <= N ? 1 : 0;
            s += dp[i];
        }
        for(int i = K - 1; i >= 0; i--) {
            dp[i] = s/W;
            s = s + dp[i] - dp[i + W];
        }
        return dp[0];
    }
}