【Hello Algorithm】暴力递归到动态规划（五）

递归到动态规划（五）"/>

【Hello Algorithm】暴力递归到动态规划（五）

死亡概率问题

现在给定你三个参数 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_cast<double>(M + 1) , K);                                                                            }                                                                                                                        if (K == 0)    {                                                                                                                                         return rest <= 0 ? 1 : 0;    }    

否则我们就要开始考虑其他可能性了

因为每一刀可能会砍0~M滴血 所以说一共会有M+1种可能 我们全部加起来就能得到最终结果

  int ways = 0;for (int i = 0; i <= M; i++){ways += process(rest - i , K - 1 , M);}return ways;

动态规划

接下来我们开始改写动态规划

首先我们观察到 可变参数有两个 血量和砍的次数

血量的变化范围是0~N+1 （其实可能会小于0 但是小于0我们能计算出来）

砍的次数的变化范围是0~K+1

我们将血量命名为hp 砍的次数命名为K+1

代码表示如下

int dp_process( int N , int K , int M)  
{  vector<vector<int>> dp(K + 1 , vector<int>(N + 1 , 0));  for (int i = 0; i <= K; i++)  {  dp[i][0] = pow(static_cast<double>(M+1) ,static_cast<double>(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(vector<int>& arr , int index , int rest)    
{    if (rest < 0)    {    return MAX_VAL;    }    if (index == static_cast<int>(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(vector<int>& arr ,  int aim)
{int N = static_cast<int>(arr.size()) ; // N = arr.size() vector<vector<int>> dp(N + 1 , vector<int>(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];
}