地下城游戏--动态规划.路径问题

地下城游戏

• 题目
• 五步走
• • 状态表示
  • 转移方程
  • 初始化
  • 填表顺序
  • 返回值
• 代码

题目

五步走

状态表示

根据经验：有两种表示方式：1，以dp[i][j]为终点+巴拉巴拉 2，以dp[i][j]位置为起点+巴拉巴拉。
我开始写的时候用的第一种方式，结果没有表示出来，第二种方法可以。
dp[i][j]表示从下标为（i，j）出发，到达终点时消耗的最小健康点数。

转移方程

根据经验：找里下标(i,j)最近的位置考虑，离下标(i,j)最近的是dp[i+1][j]和dp[i][j+1],设我要从(i,j)走到终点需要的健康点数为x，x+dungeon[i][j]就表示我走出(i,j)格子剩下的健康点数，它要满足大于等于min(dp[i+1][j],dp[i][j+1])才能到达终点。
所以dp[i][j]=min(dp[i+1][j],dp[i][j+1])-dungeon[i][j],
注意**：当算出来dp[i][j]<=0时，说明它获得的健康点数很大足已为负数了，但是如果是<=0，那么就不能继续往下走了，所以当<=0时，要变成1**。

初始化

假设m=2,n=3

绿色格子里面填什么值？ 要使绿色格子里的值不影响小圈格子，要使绿色格子里放INT_MAX，dp[m-1][n]=1or dp[m][n-1]=1

填表顺序

从下往上，右往左

返回值

dp[0][0]

代码

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        //创建dp表
        int m=dungeon.size();
        int n=dungeon[0].size();
        int dp[m+1][n+1];
        int i,j;
        //填表
        for(i=m;i>=0;i--)
        {
            for(j=n;j>=0;j--)
            {
                if(i==m||j==n&&i!=m-1)
                {
                    dp[i][j]=INT_MAX;
                }
                else if(j==n&&i==m-1)
                {
                    dp[i][j]=1;
                }
                else
                {
                    dp[i][j]=min(dp[i][j+1],dp[i+1][j])-dungeon[i][j];
                    if(dp[i][j]<=0)
                    {
                        dp[i][j]=1;
                    }
                }
            }
        }
        //返回
        return dp[0][0];
    }
};