Dungeon Game

Dungeon Game是leetcode上的一道标记Hard的题目,描述如下：

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.
The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.
Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).
In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.
Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN

example

简单解释一下题意，如上图二维矩阵，假设骑士初始生命值为h，从左上角（坐标不妨设为[0,0]）开始向右下角移动，每一次移动只能向右或向下一个格子，每经过一个宫格，生命值加上格内的数字，直到最后的右下角(坐标[m-1,n-1])，要求是每一步骑士生命值都要保证大于0，求h的最小值是多少。

解题思路

如果使用暴力的穷举算法，可以计算出共有C(m+n-2,m-1)种路径可从[0,0]到达[m-1,n-1]. 再乘以二者的曼哈顿距离m+n-2，可知算法的复杂度为（m+n-2)*C(m+n-2,m-1), 是O((m+n)!) ，是非常慢的算法，鉴于历史经验，这种解法是会被leetcode拒绝的。（关于此处公式证明，请参考下一篇文章）

动态规划

动态规划基本条件

有很看似非多项式的问题经常可以使用动态规划来实现P的解法。比如比较有名的斐波那契数列、背包问题、集合划分问题等。那这个题目能否也符合使用动态规划的条件呢，我们来分析一下。
首先，能采用动态规划求解的问题一般具有3个条件：

1. 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
2. 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
3. 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

递推公式

简单的讲，就是能否找到一个递推公式，在m*n步后推出答案。
针对这个题目，一种思路是，假设已知了[x-1,y]和[x,y-1]处所需要的起始最小生命值，能否得出[x,y]处的最小生命值吗？读者不妨思考几分钟。
答案是肯定可以计算出的，但不幸的是，当我提交代码时，碰到了如下输入：

递推所得的结果为：

这里最终的结论是需要起始生命值为5，路线为DOWN->RIGHT->RIGHT->DOWN
但实际上只需要3即可。路线为RIGHT->RIGHT->DOWN->DOWN
显然，不能仅仅根据相邻的左侧和上侧来计算最低生命值，因为违反了第二条性质。只能结合3条性质再次思考。

既然正着算不行，那我们倒着推. -M23 .
当我写到这里的时候,简书网站nginx挂掉了，然后先是降级服务，紧接着估计是回滚，大约10分钟吧。估计RD、OP有得忙了。参考下图为证:

简书宕机

正确的递推公式

从右下角出发，向左向上计算相邻节点的最小生命值，反复这个过程得到[0,0]处的，是否是正确的呢。公式如下：

其中，p代表输入矩阵。
由于是倒推，很容易用反证法来证明从[m,n] 到[m-1,n] 或[m,n-1]的结论。
根据公式来写代码，是比较简单的了。

class Solution(object):

    def calUnidirectHealth(self, m_health, x):
        return max(1, m_health - x)

    def calBidrectHealth(self, down_min, right_min, x):
        return min(self.calUnidirectHealth(down_min, x),self.calUnidirectHealth(right_min,x))

    def calculateMinimumHP(self, dungeon):
        """
        :type dungeon: List[List[int]]
        :rtype: int
        """
        m, n = len(dungeon), len(dungeon[0])
        min_health = [[0 for x in range(n)] for y in range(m)]
        min_health[-1][-1] = self.calUnidirectHealth(1,dungeon[-1][-1])

        for i in range(m - 2, -1, -1):
            min_health[i][-1] = self.calUnidirectHealth(min_health[i + 1][-1],dungeon[i][-1])
        for i in range(n - 2, -1, -1):
            min_health[-1][i] = self.calUnidirectHealth(min_health[-1][i + 1],dungeon[-1][i])

        for i in range(m - 2, -1, -1):
            for j in range(n - 2, -1, -1):
                min_health[i][j] =\
                self.calBidrectHealth(min_health[i + 1][j], min_health[i][j + 1], dungeon[i][j])
        return min_health[0][0]

总结

上述算法，使用2层for循环分别计算了各坐标处的生命值，复杂度为O(m*n)。