讯享网
题目链接:https://leetcode-cn.com/problems/new-21-game/
- 最主要还是发现一个递推关系式，设dp(i)为目前得分为i时，再抽一张牌，K<=points<=N的概率，而这个概率又与抽到下一张牌得到总分后，再抽一张牌：K<=points<=N的概率有关，而每次抽取都是等概率的,所以:
dp(i)=1/w(dp(i + 1)+dp(i + 2)...+dp(i + w)) - 边界条件:当我们目前得分是K到N时，dp(i)都为1，因为这个分数满足了条件，而
N + 1 < points <= (k - 1 + W)时，此时不满足都为0. - 递推顺序：很明显，逆推，并且从dp(K - 1)开始往前推，因为从K开始概率都确定好了。
class Solution {
public: double new21Game(int N, int K, int W) {
double dp[K + W]; for(int i = 0;i <= W + K - 1;++i){
if(K <= i && i <= N) dp[i] = 1.0; else dp[i] = 0.0; } //dp(i) = 1/w * (dp(i + 1) + ... + dp(i + w)) double t = -1.0; double S = (N - K + 1); for(int i = K - 1;i >= 0;--i){
//内存for循环可优化 // for(int j = i + 1;j <= i + W;++j) t += dp[j]; // if(t == -1.0){
// t = 0.0; // for(int j = i + 1;j <= i + W;++j) t += dp[j]; // }else{
// t -= dp[i + W + 1]; // t += dp[i + 1]; // } dp[i] = S / (double)W; S += (dp[i] - dp[i + W]); } return dp[0]; } }; 讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/72579.html