New21Game [source code]
public class New21Game {
static
/****************************************************************************/
class Solution {
public double new21Game(int N, int K, int W) {
if (K == 0 || N > K - 1 + W)
return 1;
double[] dp = new double[N + 1];
dp[0] = 1.0;
double sum = 1.0;
for (int i = 1; i < K; i++) {
dp[i] = sum / W;
sum += dp[i];
if (i >= W)
sum -= dp[i - W];
}
double res = 0.0;
for (int i = K; i <= N; i++) {
dp[i] = sum / W;
res += dp[i];
if (i >= W)
sum -= dp[i - W];
}
return res;
}
}
/****************************************************************************/
public static void main(String[] args) {
New21Game.Solution tester = new New21Game.Solution();
int[] inputs = {
10, 1, 10,
6, 1, 10,
21, 17, 10,
1,1,1,
10,8,5,
8,6,5,
};
double[] answers = {
1.0,
0.6,
0.73278,
1.0,
0.81359,
0.76499,
};
for (int i = 0; i < inputs.length / 3; i++) {
System.out.println (Printer.separator ());
int N = inputs[3 * i], K = inputs[3 * i + 1], W = inputs[3 * i + 2];
double ans = answers[i], output = tester.new21Game (N, K, W);
System.out.printf ("%d, %d, %d\n%s\n%f\n",
N, K, W, Printer.wrap (output + "", Math.abs (output - ans) < 10e-5 ? 92 : 91), ans
);
}
}
}
题目意思倒是挺清楚的, 一点思路都没有; 又是最头疼的概率题, 很无语;
例子给的倒是挺贴心的, 前两个例子是两个给你介绍题目的意图的小例子; 然后第三个例子类似是给你debug的了;
这题的DP性质其实是很明显的, 每一次draw就是一个decision level, 难点可能在实现上面;
DP问题不要偷懒, 自己画path, 或者说, draw trellis. 真的, 不要偷懒;
这题的dot概念还非常的明显, 就是你手上的分数; 一开始是0;
第三个例子好像也不是特别大, 可以用来帮助分析;
诶, 这题是不是就是一个跟sum-product差不多的一个算法啊?
又是概率, 太相似了;
不过题目最后问的东西有点奇怪, 实现上估计还是有点蹊跷的;
这个能看出来啥?
DP倒是挺明显的, 关键是这个概率怎么算?
瞎写写算了;
一个小坑是最后的res一开始声明的是int, 然后collect出来的结果怎么都是0.0, 这个很坑爹了; 完全是不仔细;
写了这个算法:
class Solution {
public double new21Game(int N, int K, int W) {
double[] dp = new double[K + W + 1];
dp[0] = 1.0;
int pos = 0;
while (pos < K) {
for (int draw = 1; draw <= W; draw++) {
int nei = pos + draw;
dp[nei] += dp[pos] * (1.0 / W);
}
pos++;
}
double res = 0.0;
for (int i = N; i >= K; i--)
res += dp[i];
return res;
}
}
感觉基本是没有毛病的, 居然被TLE了(不是算法出错, 结果是对的, 但是就是时间TLE了);
这个算法是一个比较正常向的后向的DP过程; 有点像当时forward-backward算法的时候, beta那个计算的办法; 不是parent去query自己的child, 而是child直接把subsolution主动的往parent去扔;
那么我这个其实已经是一个线性的结果了, 但是他还是认为不够快, 怎么优化? 是不是又有点数学的东西在里面?
反正大概思路也是有了, 这个解法真正面试的时候应该也是过关了, 看下答案算了;
一般来说应该尝试找一下简单的pruning, 不过说实话这题好像也没有什么特别好的pruning思路;
模仿discuss1写一个解法; 不过我故意用一个2pass, 这样好理解一些;
写的过程当中, 发现他的代码有一个很tricky的地方, 就是你看, 当i走到K开始, dp[i]照常计算, 但是这个时候窗口, 是只出不进了; 自己想想为什么: 比如你走到K了, 算了dpK; 然后这个时候你是否应该把dp[K]扔到窗口里面去呢?
很容易就知道, 不应该的, 因为后面比如你计算dp[K+1]的时候, 他是不应该考虑dp[K]的贡献的;
我这样讲起来, 是很平铺直叙的, 但是他的代码因为追求1pass, 所以最后这个隐藏的有点深的;
最后AC, 速度是19(NA). 最后一个bug是一开始我FI的header写的是i > W, 这个是有毛病的, 事实上, 等于W的时候, 也要开始退款了: 你等于W的时候, 你的窗口维护的是0..W-1, 这个时候已经可以开始退款了; 一个有点subtle的小point;
UNFINISHED
editorial
Approach #1: Dynamic Programming [Accepted]
class Solution {
public double new21Game(int N, int K, int W) {
double[] dp = new double[N + W + 1];
for (int k = K; k <= N; ++k)
dp[k] = 1.0;
double S = Math.min(N - K + 1, W);
for (int k = K - 1; k >= 0; --k) {
dp[k] = S / W;
S += dp[k] - dp[k + W];
}
return dp[0];
}
}
比了一下, 他这个就真的比我快很多, 我的最后被break的case是:
5895
3952
4172
我的算法这个跑了33ms, 他的只要1ms, 所以估计里面还是有点东西的;
感觉有点乱写啊, intuition上来就是alice wins the game, 哪里说了有win the game的定义了啊;
我的做法好像就是他描述的naive DP, 虽然顺序有点不同: 他的是一个正常的forward DP(按照forward-backward algorithm的beta来理解前还是后就行了); 我的是一个backward DP;
但是复杂度确实都是他分析的这个;
他这个优化有点看不懂, 就是f(x)-f(x-1)这里的;
大概是这个意思, 思路是对的, 但是感觉他写的时候有笔误? 应该是f(x)-f(x-1)=(1/W)(f(x)-f(x-W-1))才对;
again, 用具体的例子来帮助理解;
先不纠结具体的细节, 看看有了这个思想之后, 能不能帮助加速;
不对, 他这个计算好像跟我不一样, 重新看他的定义:
Let f(x) be the answer when we already have x points. Clearly, f(x) = 1.0 when K <= x <= N, and f(x) = 0.0 when x > N.
这个解释好像说得通了, 所以他的f定义的实际上是, 如果我现在手上有x分, 我最后能win, 也就是按照规则不停的draw直到停止, 最后手上的分数≤N的概率;
他这个定义跟我的定义差别还是挺大的, 不是简单的直接每一个cell存放的实际上就是最后停在这个cell的概率;
那么他上面这句话就基本能理解了;
S按照他的描述, 是一个固定大小等于W的滑动窗口;
首先你要理解这个式子, 这个有点讲究:
这个跟我的定义方式下的这个式子计算很类似, 但是只是看起来类似而已; 实际上, 他这个问题, 最后反而是后面, 也就是x很大的时候, 是base case: K..N的范围内是1.0, N+1.. 范围是0.0.
然后对于更小的x, 我们只要向后看W个位置, 类似于你站在x向后伸出去W个触手. 第一个level, 你可以这样想, 有几个触手落在了1.0的上面, 有几个落在了0.0的上面;
然后求和就行了; 这个是不是也是哪里见过的?
这个DP居然最后直接就是target value作为dp value, 也是没有想到;
理解了这个, 就可以看他下面的这个优化了;
注意, 应该很清楚他这个x是从后往前扫的了; 每一个x, 则是向后查询;
f(x)查询f(x+1..x+W), f(x-1)查询f(x..x+W-1); 那么他的:
就不是特别难理解了;
他这个推导是没有毛病的;
重新改写一下;
所以实际上维护的这个窗口应该是size W-1的? 跟他的描述有点出入;
我日, 我看懂了, 其实他这里故弄玄虚, f(x)-f(x-1)这个式子根本就没有用到; 实际上只用到了一开始f(x)=sum(f(x+1)..f(x+W))这个式子; 然后因为是一个从右到左的倒着来的DP, 所以直接维护这个长度是W的窗口就行了;
这个是看上面那个(21,17,10)的数字trace的第一个iteration的时候理解到的他在干什么; 所以说理解算法还是要靠具体的例子.
然后整个算法其实就很简单了;
他这个思路的难点在于一个是知道在后面定义base case: 这个并不是那么容易想到; 相对于我的那个path probablility at end cell的定义, 他这个定义更加的subtle;
另外一个难点就是这个滑动窗口设计; 按理说看到这里adjacent range sum的DP结构, 应该是能够想到这个优化的, 这个优化其实是见到过好几次的了;
这也是这题为什么只是medium, 尽管看起来好像用了不少的小技巧; LeetCode看来这些都是常见的DP技巧, 我们应该会才对;
唯一一个遗留问题, 就是S的初始值这里的min(N - K + 1, W). 这个其实也不难理解; S最开始的初始值, 一开始的这个窗口, 实际上是为了f(K-1)服务的; 你想想, K-1查询的应该是哪些? 实际上就是从K..K+W.
一个更直接的方法是直接走一个sum; 但是实际上你想想, W的长度只有两种情况, 从K开始的话, K+W要么超过了N, 要么没有超过;
如果超过了, 那么我们的sum就是这个min的第一项; 如果没有超过N, 那么我们的这个sum就是min的第二项;
分析到这里这个算法基本就理解了; 比较tricky的还是这个定义的发掘;
看了他这个算法, 我感觉我的那个算法, 也是可以优化的, 尤其是里面那个对W的for循环;
https://leetcode.com/problems/new-21-game/discuss/132334/One-Pass-DP
Intuition:
The same problems as "Climbing Stairs".Explanation:
In a word,
dp[i]: probability of get points i
dp[i] = sum(last W dp values) / WTime Complexity:
O(N)
public double new21Game(int N, int K, int W) {
if (K == 0 || N >= K + W) return 1;
double dp[] = new double[N + 1], Wsum = 1, res = 0;
dp[0] = 1;
for (int i = 1; i <= N; ++i) {
dp[i] = Wsum / W;
if (i < K) Wsum += dp[i]; else res += dp[i];
if (i - W >= 0) Wsum -= dp[i - W];
}
return res;
}
还没认真看, 不过看起来好像是一个跟我的定义类似的, 所以没有awice那个tricky定义的难度; 然后也没有uwi那个[0]=-1的很tricky的初始化的设定;
这个家伙感觉讲解比以前进步了, 最起码比如这里的DP的定义, 是给的很清楚了;
我热, 看完之后, 发现这题好简单? awice那个写法, 直接就是一个从右到左的时候, 维护一个窗口;
我的这个写法, 直接从左到右的时候, 也维护一个窗口就行了啊;
感觉是被awice和uwi组团忽悠进去了;
自己实现看看, 这个应该没问题了;
uwi: 10分钟
class Solution {
public double new21Game(int N, int K, int W) {
double[] dp = new double[N+3];
dp[0] = 1;
dp[1] = -1;
double val = 0;
for(int i = 0;i < K;i++){
val += dp[i];
if(i+1 <= N)dp[i+1] += val / W;
if(i+W+1 <= N)dp[i+W+1] -= val / W;
}
double ret = 0;
for(int i = K;i <= N;i++){
val += dp[i];
ret += val;
}
return ret;
}
}
他这个算法很多地方跟我第一版本的TLE算法就很类似, 比如第二个for循环的这俄格K..N的sum, 然后第一个for循环也是一个从0..K-1的更新过程;
或许他这个就是对应我的定义的DP写法; 理解看看; 我自己看完editorial的时候想了一下怎么用那个类似的办法来优化我自己的算法, 但是没有什么好思路, 几乎都要放弃了;
所以说看uwi的解法还是很有启发的; 说实话awice的那个f的定义方式真的不是特别好想到了; 现在DP题目做多了, 这种target value直接作为dp value的反而都不敢写了;
重新多思考了一会儿, 大概是理解了他的逻辑了, 只能说uwi是真的聪明;
看不懂的时候, 还是自己多展开一些iteration, 看看计算的到底是什么东西;
这个图应该就看的很清楚了;
核心的思想, 就是比如W=5的时候, 我们最后f(7), 需要的就是sum(f(2)..f(6))的意思; 这个是一个固定size的window, 或者说是一个difference, 这个东西我们以前是碰到过的, 事实上, sum(f(2)..f(6))=sum(f(0)..f(6)) - sum (f(0)..f(1)). 这个就是他第一个循环里面的核心逻辑, 非常的聪明;
唯一不懂跟但是他dp[1]为什么要初始化到-1; 打trace看看;
========================
1.0 -0.9 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0
10, 1, 10
0.9999999999999998
1.000000
========================
1.0 -0.9 0.0 0.0 0.0 0.0 0.0 0.0 0.0
6, 1, 10
0.5999999999999999
0.600000
居然还是对的;
好像这个计算跟他第二个循环里面的计算也有关系, 他第二个循环里面不是直接就collect DP的value, 而是有一个对val的修改操作, 然后ret最后收集的是val而不是dp本身;
他这个DP写法严格来说也是一个backward的写法; 不过比我的巧妙很多;
看他第一个循环的具体的写法, i的上限是K-1, 但是后面i向后peek的上限是N, 这个他的定义也是非常清楚的, 大概思考一下应该能理解背后的原理;
看看他第二个循环算的到底是什么:
========================
i:(0), val:(1.000000), dp: 1.0 -0.9 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0
i:(1), val:(0.100000), ret:(0.100000)
i:(2), val:(0.100000), ret:(0.200000)
i:(3), val:(0.100000), ret:(0.300000)
i:(4), val:(0.100000), ret:(0.400000)
i:(5), val:(0.100000), ret:(0.500000)
i:(6), val:(0.100000), ret:(0.600000)
i:(7), val:(0.100000), ret:(0.700000)
i:(8), val:(0.100000), ret:(0.800000)
i:(9), val:(0.100000), ret:(0.900000)
i:(10), val:(0.100000), ret:(1.000000)
10, 1, 10
0.9999999999999998
1.000000
========================
i:(0), val:(1.000000), dp: 1.0 -0.9 0.0 0.0 0.0 0.0 0.0 0.0 0.0
i:(1), val:(0.100000), ret:(0.100000)
i:(2), val:(0.100000), ret:(0.200000)
i:(3), val:(0.100000), ret:(0.300000)
i:(4), val:(0.100000), ret:(0.400000)
i:(5), val:(0.100000), ret:(0.500000)
i:(6), val:(0.100000), ret:(0.600000)
6, 1, 10
0.5999999999999999
0.600000
没想到这个问题比我想象的复杂很多; 我现在想要解决的问题:
- why does he do this?
- can we do without this trick?
不行, 给的例子不太好, 我还是自己做几个例子;
这个例子感觉不错:
========================
i:(0), val:(1.000000), dp: 0=1.000000 1=-0.800000 2=0.000000 3=0.000000 4=0.000000 5=0.000000 6=-0.200000 7=0.000000 8=0.000000 9=0.000000 10=0.000000
i:(1), val:(0.200000), dp: 0=1.000000 1=-0.800000 2=0.040000 3=0.000000 4=0.000000 5=0.000000 6=-0.200000 7=-0.040000 8=0.000000 9=0.000000 10=0.000000
i:(2), val:(0.240000), dp: 0=1.000000 1=-0.800000 2=0.040000 3=0.048000 4=0.000000 5=0.000000 6=-0.200000 7=-0.040000 8=-0.048000 9=0.000000 10=0.000000
i:(3), val:(0.288000), dp: 0=1.000000 1=-0.800000 2=0.040000 3=0.048000 4=0.057600 5=0.000000 6=-0.200000 7=-0.040000 8=-0.048000 9=0.000000 10=0.000000
i:(4), val:(0.345600), dp: 0=1.000000 1=-0.800000 2=0.040000 3=0.048000 4=0.057600 5=0.069120 6=-0.200000 7=-0.040000 8=-0.048000 9=0.000000 10=0.000000
i:(5), val:(0.414720), dp: 0=1.000000 1=-0.800000 2=0.040000 3=0.048000 4=0.057600 5=0.069120 6=-0.117056 7=-0.040000 8=-0.048000 9=0.000000 10=0.000000
i:(6), val:(0.297664), ret:(0.297664)
i:(7), val:(0.257664), ret:(0.555328)
i:(8), val:(0.209664), ret:(0.764992)
8, 6, 5
0.7649919999999995
0.764990
看这个trace, 感觉在6..8(也就是K..N)的时候, 你做的事情其实跟前面做的事情是很类似的, 都是在sum to val. 但是一个区别是你在这个区间的时候, 你不用像跟0..5那样的时候, 还要向后peek; 这个也是题目意思决定的, 当你走到这个分数的时候, 就没有必要去更新后面的了: 你不能再draw了;
那还是很奇怪, 比如6, 最后贡献的就是sum(dp(0)..dp(6)), 为什么呢? 为什么不是直接是dp(6)呢? 有什么技巧在里面?
当然, 我是理解为什么直接的做法不行的, 比如你看上面之前那个6,1,10的简单的例子, 你最后实际上DP只被更新了一次, 如果你dp(1)初始化到0, 你最后DP样子就是1 0.1 0 0 0...这样的, 你对dp(K..N)的sum最后是无法得到0.6的; 这个主要是因为2..后面这一段根本没有得到更新的机会;
我想到另外一种解释, 就是dp的定义其实是dp[i] is the difference between prob of path to i and prob of path to i-1. 之所以这样想是因为上面说的, prob of path to i = sum(dp[0]..dp[i]), 那么sum(dp[0]..dp[i-1]) + dp[i] = sum(dp[0]..dp[i]), 也就是dp[i] = pathprob to i minus pathprob to i-1;
但是这个解释有一个问题就是, 怎么解释第一个循环的计算? 当你在i的时候, sum/val其实就是path prob to i, 你为什么可以用这个来更新dp[i+1] and dp[i+W+1], 注意, 这两个不是pathprob, 而是两个difference了;
所以感觉还是很难解释;
没有给DP想到一个合理的定义之前, 我都没有办法去解释这个[1]=-1的初始值到底是什么意思;
这个dp is pathprob diff的定义, 其实是可以比较不错的解释之前的6,1,10那个例子的; 包括-1这个初始化;
当然, 对应到代码上面之后, 我还是没有办法完美的解释;
暂时没有时间了, 先不看这个了, 看一下discuss的最优解;
Problem Description
Alice plays the following game, loosely based on the card game "21".
Alice starts with 0 points, and draws numbers while she has less than K points. During each draw, she gains an integer number of points randomly from the range [1, W], where W is an integer. Each draw is independent and the outcomes have equal probabilities.
Alice stops drawing numbers when she gets K or more points. What is the probability that she has N or less points?
Example 1:
Input: N = 10, K = 1, W = 10
Output: 1.00000
Explanation: Alice gets a single card, then stops.
Example 2:
Input: N = 6, K = 1, W = 10
Output: 0.60000
Explanation: Alice gets a single card, then stops.
In 6 out of W = 10 possibilities, she is at or below N = 6 points.
Example 3:
Input: N = 21, K = 17, W = 10
Output: 0.73278
Note:
- 0 <= K <= N <= 10000
- 1 <= W <= 10000
- Answers will be accepted as correct if they are within 10^-5 of the correct answer.
- The judging time limit has been reduced for this question.
Difficulty:Medium
Total Accepted:509
Total Submissions:2.5K
Contributor:lee215
Companies
google
Related Topics
dynamic programming