广告推广营销网站,网页制作与设计专业,优品ppt官网网址,微信接口文档死亡概率问题
现在给定你三个参数 N M K
怪兽有 N 滴血 等着英雄来砍自己
英雄每一次打击会让怪兽流失 0 ~ M 滴血 概率相同
请求在K次之后 英雄把怪兽砍死的概率
递归版本
面对这个问题 我们首先来想递归函数怎么写
首先是返回值 我们无法直接返回一个概率给上层 所以我…死亡概率问题
现在给定你三个参数 N M K
怪兽有 N 滴血 等着英雄来砍自己
英雄每一次打击会让怪兽流失 0 ~ M 滴血 概率相同
请求在K次之后 英雄把怪兽砍死的概率
递归版本
面对这个问题 我们首先来想递归函数怎么写
首先是返回值 我们无法直接返回一个概率给上层 所以我们这里决定返回怪兽死去的次数 只要上层用所有的可能性相除就能得到概率了
接下来就是将相关的参数填到函数中 因为怪兽剩余的血量是变化的 所以说我们不使用N作为参数 而是使用rest – 怪兽的剩余血量作为参数
int process(int rest , int K , int M)我们首先来想base case
如果剩余血量为0 如果砍的刀数等于0此时都会结束 if (rest 0) { return pow(static_castdouble(M 1) , K); } if (K 0) { return rest 0 ? 1 : 0; } 否则我们就要开始考虑其他可能性了
因为每一刀可能会砍0~M滴血 所以说一共会有M1种可能 我们全部加起来就能得到最终结果 int ways 0;for (int i 0; i M; i){ways process(rest - i , K - 1 , M);}return ways;动态规划
接下来我们开始改写动态规划
首先我们观察到 可变参数有两个 血量和砍的次数
血量的变化范围是0~N1 其实可能会小于0 但是小于0我们能计算出来
砍的次数的变化范围是0~K1
我们将血量命名为hp 砍的次数命名为K1
代码表示如下
int dp_process( int N , int K , int M)
{ vectorvectorint dp(K 1 , vectorint(N 1 , 0)); for (int i 0; i K; i) { dp[i][0] pow(static_castdouble(M1) ,static_castdouble(K)); } for (int times 1; times K; times) { for(int hp 1; hp N; hp) { int ways 0; for (int i 0; i M; i) { if (hp - i 0) { ways dp[times - 1][hp - i]; } else { ways dp[times-1][0]; } } dp[times][hp] ways; } } return dp[K][M]; }钱包问题四
arr是面值数组 其中的值都是正数且没有重复 给定一个正整数aim 返回组成aim的最小货币张数
我们首先来想base case
如果剩余的钱数小于0 那么我们无法找到最小张数
如果数组下标超过了arr 此时我们就需要分情况讨论
如果此时rest为0 则0张就可以解决如果此时resr不为0 则无解
接下来我们就可以开始列可能性
我们可以选择0 ~ N张arr[index]的货币 之后将剩余的钱和下标交给下面的位置就可以
const int MAX_VAL INT32_MAX; int process(vectorint arr , int index , int rest)
{ if (rest 0) { return MAX_VAL; } if (index static_castint(arr.size())) { return rest 0 ? 0 : MAX_VAL; } int ways MAX_VAL; for (int fix 0; fix * arr[index] rest; fix) { int Next process(arr , index 1 , rest - fix*arr[index]); if(Next ! MAX_VAL) { ways min(ways , Next fix); } } return ways;
} 动态规划
我们可以看到两个变化的量是index 和 rest
index的变化范围是 0 ~ arr的大小
rest的范围是 0 ~ aim
于是我们可以围绕着代码建立一个二维表
之后按照上面的递归代码改写即可 代码表示如下
int dp_process(vectorint arr , int aim)
{int N static_castint(arr.size()) ; // N arr.size() vectorvectorint dp(N 1 , vectorint(aim 1 , MAX_VAL));// base case // 1. rest 0 ? -1 // dp[N][0] 0;for (int index N -1 ; index 0 ; index--) {for(int rest 0; rest aim; rest){int ways MAX_VAL;for (int fix 0; fix * arr[index] rest; fix){int Next dp[index 1][rest - fix*arr[index]];if(Next ! MAX_VAL){ways min(ways , Next fix);}}dp[index][rest] ways;}}return dp[0][aim];
}
