(https://leetcode-cn.com/problems/new-21-game/)
这是我第二次见用dp直接求值的题目,以往只知道dp在求最值时用的最多,而且这题是个从后往前的dp,而不是从前往后,开阔了眼界,挺好的一道题
如果不会做的话就看这个题解吧https://leetcode-cn.com/problems/new-21-game/solution/huan-you-bi-zhe-geng-jian-dan-de-ti-jie-ma-tian-ge/,我也是看题解做的,没办法,dp这种题就只能多见多写多积累
这里只说我对状态转移方程的理解
[dp[x]=1/w * (dp[x+1]+dp[x+2]+dp[x+3]...+dp[x+w])
]
在写转移方程的时候要时时刻刻记着状态代表的意思,dp[i] 表示刚开始手里的点数是i,并且最终能赢的概率,那么答案就是要求dp[0] ,接下来就是找关系,假如要求dp[x] ,我们要去想dp[x]与后面的dp有什么关系。
举个最简单的例子,假如我们现在知道了手里点数为6的时候赢的概率是0.5,我们现在想知道手里点数为5的时候赢的概率,如果我们抽牌抽到1的概率是1,那么很明显p(5) = p(6) = 0.5,但如果我们抽到1的概率为0.5,那么p(5) = p(6)*0.5 = 0.25,,应该不难理解,我只有抽到1才有0.5的概率赢,但我现在连抽到1的概率只有0.5,那么我能赢的概率就只有0.25了
回到这题,当前我们手中的点数为x,我们现在可以抽到的点数为T(1 <= T <= w ),概率为1/w,我们又知道了dp[x+T]的概率,所以dp[x] = dp[x+T]/w,展开就得到了转移方程
class Solution {
public:
double new21Game(int N, int K, int W) {
double dp[K+W];
for(int i = K; i < K+W; i++){
if(i <= N) dp[i] = 1;
else dp[i] = 0;
}
double sum = 0;
for(int i = K; i < K+W; i++) sum += dp[i];
for(int i = K-1; i >= 0; i--){
dp[i] = sum / W;
sum = sum+dp[i]-dp[i+W];
}
return dp[0];
}
};