(nice!!!)(LeetCode 每日一题) 837. 新 21 点 (动态规划、数学)
题目:837. 新 21 点
思路:动态规划+数学,时间复杂度0(n)。
细节看注释。
C++版本:
class Solution {
public:double new21Game(int n, int k, int maxPts) {// 状态f[i]表示:在i分的情况下,到达分数区间[k,n]的概率。vector<double> f(n+1,0);// s表示 f[i+1]~f[i+maxPts]的概率之和// 因为i是从后往前,所以最初的s和为0double s=0;for(int i=n;i>=0;i--){// 当i>=k,说明此时i就在分数区间[k,n],这时概率为1// 当i<k,说明到达[k,n]的概率是(f[i+1]~f[i+maxPts]的概率之和)/maxPtsf[i]= i>=k ? 1:s/maxPts ;// 维护下一个i-1的ss+=f[i];if(i+maxPts<=n) s-=f[i+maxPts];}return f[0];}
};
JAVA版本:
class Solution {public double new21Game(int n, int k, int maxPts) {double[] f=new double[n+1];double s=0;for(int i=n;i>=0;i--){f[i]= i>=k ? 1:s/maxPts ;s+=f[i];if(i+maxPts<=n) s-=f[i+maxPts];}return f[0];}
}
GO版本:
func new21Game(n int, k int, maxPts int) float64 {f:=make([]float64,n+1)var s float64 =0for i:=n;i>=0;i-- {if i>=k {f[i]=1}else{f[i]=s/float64(maxPts)}s+=f[i]if i+maxPts<=n {s-=f[i+maxPts]}}return f[0]
}