动态规划-杀死那只怪兽-斜率优化
问题描述
给定3个参数，blood，hurt，hitTime 。怪兽有 blood 滴血，等着英雄来砍自己。英雄每一次打击，都会让怪兽流失 [0~hurt] 的血量（此区间上等概率选定一个整形值）。求经过 hitTime 次打击之后，英雄把怪兽砍死的概率。
暴力递归
每次击打会扣除 [0~hurt] 范围上任意整形值的血量，一共击打 hitTime 次，所以最后剩余血量有 (hurt+1)^{hitTime} 种可能（包含负值）。注意，如果剩余击打次数还没有到 0 怪兽就已经死亡，死后仍需要继续鞭打（俗称鞭尸，哈哈），直到剩余击打次数 0 时才能停止，然后检查怪兽是否死亡，如果已死亡则返回 1 ，否则返回 0 。代码很简单：
double process(int hurt, int restHit, int restBlood)
{
if(restHit <= 0)
{
if(restBlood <= 0)
return 1;
else
return 0;
}
double die = 0;
for(int h = 0; h <= hurt; h++)
die += process(hurt, restHit - 1, restBlood - h);
return die;
}
double killMonster(int blood, int hurt, int hitTime)
{
double all = pow(hurt + 1, hitTime);
double die = process(hurt, hitTime, blood);
return die / all;
}
动态规划
对比暴力递归，很容易得到动态规划：
//help专门处理边界条件
double help(int restHit, int restBlood, int hurt, const vector<vector<double>> &dp)
{
if(restHit <= 0)//此处==需要改为<=
{
if(restBlood <= 0)
return 1;
else
return 0;
}
return dp[restHit][restBlood];
}
double killMonster(int blood, int hurt, int hitTime)
{
vector<vector<double>> dp(hitTime + 1, vector<double>(blood + 1, 0));
for(int r = 0; r <= hitTime; r++)
{
for(int c = 0; c <= blood; c++)
{
double die = 0;
for(int h = 0; h <= hurt; h++)
{
die += help(r-1, c-h, hurt, dp);
}
dp[r][c] = die;
}
}
return dp[hitTime][blood] / pow(hurt + 1, hitTime);
}
其实上面的代码还存在一个较为隐蔽的问题：在暴力递归中 restBlood 可以为负数，但改为动态规划时，dp 的列序号（blood）只能为正数 。所以这里的动态规划忽略了 blood 为负数的情况。由于最小负数为 blood-hurt×hitTime ，其绝对值可能很大，如果还为负数建表，空间复杂度则较大。思考后可以发现一个事实：当 restBlood 已经小于 0 时，无论后续扣血的方式如何，最终一定会 return 1，即后续每一种扣血方式最终都会被算进死亡数 。容易知道后续的扣血方式一共有 (hurt+1)^{restHit} 种 ，所以改进暴力递归如下：
double process(int hurt, int restHit, int restBlood)
{
if(restHit <= 0)
{
if(restBlood <= 0)
return 1;
else
return 0;
}
if(restBlood <= 0)//也算一种剪枝优化
return pow(hurt + 1, restHit);
double die = 0;
for(int h = 0; h <= hurt; h++)
{
die += process(hurt, restHit - 1, restBlood - h);
}
return die;
}
进而得到正确的动态规划：
double help(int restHit, int restBlood, int hurt, const vector<vector<double>> &dp)
{
if(restHit <= 0)
{
if(restBlood <= 0)
return 1;
else
return 0;
}
if(restBlood <= 0)
return pow(hurt + 1, restHit);
return dp[restHit][restBlood];
}
//killMonster函数同上
斜率优化
以上动态规划的表依赖关系 die += help(r-1, c-h, hurt, dp) 如下图：
容易发现：(x,y) 依赖的是第 x-1 行中 [y-hurt, y] 范围上的值，类似的，(x,y+1) 依赖的是第 x-1 行中 [y+1-hurt, y+1] 范围上的值。 从上图中能看到这两者的依赖有很大的重叠部分，这就是可以优化的地方。具体来说， (x,y) 的依赖可以转换为:
(x,y-1) + (x-1,y) - (x-1,y-hurt-1)
这样我们就成功省去了 for 循环。于是得到以下代码：
//help同上
double killMonster(int blood, int hurt, int hitTime)
{
vector<vector<double>> dp(hitTime + 1, vector<double>(blood + 1, 0));
for(int r = 0; r <= hitTime; r++)
{
for(int c = 0; c <= blood; c++)
{
dp[r][c] = help(r, c-1, hurt, dp) + help(r-1, c, hurt, dp) - help(r-1 ,c-hurt-1, hurt, dp);
}
}
return dp[hitTime][blood] / pow(hurt + 1, hitTime);
}
死亡率=1-生存率
上面的方法中，最麻烦的是处理 restBlood 为负数时的情况。实际上，将求死亡率转换为求生存率就可以绕过这个步骤。
double help(int restHit, int restBlood, int hurt, const vector<vector<double>> &dp)
{
if(restHit <= 0)
{
if(restBlood > 0)//砍完发现还有血,则生存数+1
return 1;
else
return 0;
}
if(restBlood <= 0)//由于统计的是生存数,已经砍死就不需要继续了
return 0;
return dp[restHit][restBlood];
}
double killMonster(int blood, int hurt, int hitTime)
{
vector<vector<double>> dp(hitTime + 1, vector<double>(blood + 1, 0));
for(int r = 0; r <= hitTime; r++)
{
for(int c = 0; c <= blood; c++)
{
dp[r][c] = help(r, c-1, hurt, dp) + help(r-1, c, hurt, dp) - help(r-1 ,c-hurt-1, hurt, dp);
}
}
return 1 - dp[hitTime][blood] / pow(hurt + 1, hitTime);//死亡率=1-生存率
}
总结
本题易错点：
- 当怪兽死亡后，就返回 1，不再继续鞭尸。而实际上需要继续鞭尸，鞭到 T = 0 时才能停下来，然后检查怪兽是否死亡。为什么要鞭尸，这个问题在醉汉死亡率中更能清楚体现。
- 暴力递归的状态变量 restBlood 可以为负，而动态规划的 dp 表却忽略了负数的情况，所以
help中要处理 restBlood <= 0 的情况。 - process 的返回值应为 double ，int 和 long 都容易溢出。
- killMonster 为什么不能用“要或不要”模型（对 index 指向的伤害值要或不要）？因为有 restHit 限制，导致可能出现这样的情况：只砍了怪兽 3 刀，怪兽还没死，但 index 却来到了末尾。
- 当暴力递归中出现 for 循环时，可以在动态规划中尝试斜率优化，须仔细观察位置依赖，一定要举例并画图！
- 遇到这种概率 odds ，不妨从 odds 和 1 - odds 两个方向试试。