LeetCode -- Dungeon Game

public class Solution {    private List<int> _result;    private int _row;    private int _col;    public int CalculateMinimumHP(int[,] dungeon)     {    	_result = new List<int>();    	_row = dungeon.GetLength(0);    	_col = dungeon.GetLength(1);    	    	Dfs(dungeon, 0,0,0,0);    	var min = _result.Min();    	return min;    }        public void Dfs(int[,] game, int r, int c, int minHp, int hp)    {    	hp += game[r,c];    	if(hp <= 0 && hp < minHp){    		minHp = hp ;    	}    	    	// check ending     	if((r == _row-1) && (c == _col-1)){    		if(minHp < 0){    			_result.Add(1-minHp);    		}else{    			_result.Add(1);    		}    		    		return ;    	}    	if (r < _row - 1){    		Dfs(game, r + 1, c, minHp, hp);    	}    	if (c < _col - 1){    		Dfs(game, r, c + 1, minHp, hp);    	}    }}解法二：使用dp。从右下角考虑所需最小血量，minHp[row-1,col-1] = Math.Max(1-dungeon[row-1,col-1],1);初始化边界值。向上走或向左走，取最小值：dp[i,j] = Min(dp[i+1,j]-dungeon[i+1,j], dp[i,j+1]-dungeon[i,j])dp[0,0]为解。实现代码：
public class Solution {       public int CalculateMinimumHP(int[,] dungeon)     {    	var row = dungeon.GetLength(0);    	var col = dungeon.GetLength(1);    	    	// the min hp to have    	var dp = new int[row, col];    	dp [row-1, col-1] = MinHp(1- dungeon[row-1,col-1]);    	    	// set last row    	for (var i = col - 2;i >= 0; i--){    		dp[row-1,i] = MinHp(dp[row-1,i+1] - dungeon[row-1,i]);    	}    	    	// set last col    	for (var i = row - 2;i >= 0; i--){    		dp[i,col-1] = MinHp(dp[i+1,col-1] - dungeon[i,col-1]);    	}    	    	for (var i = row-2;i >= 0;i --){    		for (var j = col - 2; j >= 0; j--){    			// come down or right    			dp[i,j] = Math.Min(MinHp(dp[i+1,j] - dungeon[i,j]),MinHp(dp[i,j+1] -dungeon[i,j]));    		}    	}    	    	return dp[0,0];    }            private int MinHp(int x){    	return  Math.Max(x, 1);    }}