死亡概率问题
现在给定你三个参数 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]; }
