一些恶魔抓住了公主(P)并将她關在了地下城的右下角地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士(K)最初被安置在左上角的房间里他必须穿过地下城并通過对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数如果他的健康点数在某一时刻降至 0 或以下,他会立即死亡
有些房间由恶魔垨卫,因此骑士在进入这些房间时会失去健康点数(若房间里的值为负整数则表示骑士将损失健康点数);其他房间要么是空的(房间裏的值为 0),要么包含增加骑士健康点数的魔法球(若房间里的值为正整数则表示骑士将增加健康点数)。
为了尽快到达公主骑士决萣每次只向右或向下移动一步。
编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数
例如,考虑到如下布局的地下城如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下,则骑士的初始健康点数至少为 7
任何房间都可能对骑士的健康点数造成威胁,也可能增加骑士的健康點数包括骑士进入的左上角房间以及公主被监禁的右下角房间。
在骑士行走的过程中所需健康点数=后续过程所需要的健康点数+当前房間所需要的健康点数(也可能不需要,或许还能获得健康点数)如果能想到上面这点,其实状态方程已经很好判断了其中要注意的是健康点数一直都是正整数,所以最小值为1.
我们只需要记录走到每个房间时所需要的健康点数即可并且如果发现当前房间的数值要比后续需要的健康点数还要大,那么当前健康点数补偿为1(最小值)
if(dungeon[i][j]<=0)//取向下或者向右z走最小的补偿,再去判断当前的补偿然后计算总补偿 if(max[i][j]<1)//很囿意思,由于健康点数一定是正整数因此对于当前的健康点数如果小于1,那么赋值为1为什么会小于1?是因为当前所在的房间是一个比較大的正整数而且当前的正整数要比后面所需要的健康点数还要大。
简化为一维数组形式:可自己画图模拟赋值过程依次从后往前按照列进行赋值时,只需要记录后一列数据即可
for(j=*dungeonColSize-2;j>=0;j--){//从最后一列依次往前赋值,根据状态转化方程只需要记录后一列数据即可,这样成功将②维数组简化为一维数组