LeetCode 174 地下城游戏

  • 结果

LeetCode 174 地下城游戏

  • 分析

    解题思路是从右下角往左上角走,每次只能向左或者向上走一步。dp[i][j]表示到达dungeon[i][j]时所需要的最少血量,这样一来这道题就变的简单了,具体代码如下,但是需要注意的是,我把初始化m-1列和n-1行的代码这部分需要初始化的代码和不需要初始化的代码写到了一起,这样做的好处是减少了两次for循环,坏处是,不如把需要特殊处理的代码独立出来可读性强。

  • 代码
 class Solution { public:     int calculateMinimumHP(vector<vector<int>>& dungeon) {         int m = dungeon.size();         int n = dungeon[0].size();         int ans;         if(m + n == 0) return ans = 0;          int dp[m][n];          for(int i = m - 1; i >= 0; i --){             for(int j = n - 1; j >= 0; j--){                 if(i == m - 1){                     if(j == n - 1){//处理最右下角的数据                         dp[i][j] = dungeon[i][j] > 0 ? 1 : 1 - dungeon[i][j];                     }else{//处理最后一行的数据                         int temp = dp[i][j + 1] - dungeon[i][j];                         dp[i][j] = temp <= 0 ? 1 : temp;                     }                     continue;                 }                  if(j == n - 1){//处理最后一列的数据                     int temp = dp[i  + 1][j] - dungeon[i][j];                                     dp[i][j] = temp <= 0 ? 1 : temp;                     continue;                 }                 int temp1 = dp[i  + 1][j] - dungeon[i][j];                 int temp2 = dp[i][j + 1] - dungeon[i][j];                 dp[i][j] = min((temp1 <= 0 ? 1 : temp1), (temp2 <= 0 ? 1 : temp2));             }         }          return dp[0][0];     } };

 

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » LeetCode 174 地下城游戏

提供最优质的资源集合

立即查看 了解详情