Taking recursion solution to linear solution
step 1 wirte recursion solution\n\n\ndouble solver(int n, int k, int mp,int sr, vector<double>&dp)\n    {\n        if(sr>=k)\n            return sr<=n?1:0;\n   
step 1 wirte recursion solution\n\n```\ndouble solver(int n, int k, int mp,int sr, vector<double>&dp)\n    {\n        if(sr>=k)\n            return sr<=n?1:0;\n        \n        if(dp[sr]!=-1)\n            return dp[sr];\n        \n        double ans=0;\n        for(int i=1;i<=mp;i++)\n        {\n            ans+=solver(n,k,mp,sr+i,dp);\n        }\n        \n        return dp[sr]=(double)ans/mp;\n    }\n    double new21Game(int n, int k, int mp) {\n        \n        vector<double>dp(k+mp,-1.00);\n        \n        return solver(n,k,mp,0,dp);\n    }\n```\n\n\n\nstep 2  wirte array dp from above recursion\n\n```\ndouble new21Game(int n, int k, int mp) {\n\n\t double dp[k+mp];\n\n   for(int i=k+mp-1;i>=k;i--)\n   {\n\t   if(i<=n)\n\t\t   dp[i]=1;\n\t   else\n\t\t   dp[i]=0;\n   }\n\n   for(int i=k-1;i>=0;i--)\n   {\n\t   double ans=0;\n\n\t   for(int j=1;j<=mp;j++)\n\t   {\n\t\t   ans+=dp[i+j];\n\t   }\n\n\t   dp[i]=ans/mp;\n   } \n\n\treturn dp[0];\n\n\t\t\t\t}\n```\n\n\n\nstep 3 realizing that the value inside j loop can be calculated be prefix sum or sliding window;\t\n```\ndouble new21Game(int n, int k, int mp) {\n\n   double dp[k+mp];\n\n\tdouble sum=0;\n\n   for(int i=k+mp-1;i>=k;i--)\n   {\n\t   if(i<=n)\n\t\t   dp[i]=1;\n\t   else\n\t\t   dp[i]=0;\n\n\t   sum+=dp[i];\n   }\n\n\n   for(int i=k-1;i>=0;i--)\n   {\n\n\t   dp[i]=sum/mp;\n\n\t   sum+=dp[i];\n\t   sum-=dp[i+mp];\n   } \n\n\treturn dp[0];\n}\n\n```\n\n
['Dynamic Programming']