day36.[滑动窗口].837.新21点

思路

动态规划

代码

var new21Game = function(N, K, W) {
 const dp = [1]
 let count = 0;
 for (let i = 1; i < N + 1; i++) {
   if (i - W - 1 >= 0) {
     count -= dp[i - W - 1];
   }
   if (i - 1 < K) {
     count += dp[i - 1]
   }
   dp[i] = count * (1 / W);
 }
 let res = 0;
 for (let i = K; i <= N; i++) {
   res += dp[i];
 }
 return res;
};

复杂度

• 时间复杂度 #card=math&code=O%28N%29)
• 空间复杂度 #card=math&code=O%28N%29)