【动态规划】地下城游戏

题目链接：https://leetcode.cn/problems/dungeon-game/description/

classSolution{public:intcalculateMinimumHP(vector<vector<int>>&d){/*时空复杂度O(mn)*/intm=d.size(),n=d[0].size();// 1. 创建dp表vector<vector<int>>dp(m+1,vector<int>(n+1,INT_MAX));// 2. 初始化dp[m-1][n]=dp[m][n-1]=1;// 3. 填表for(inti=m-1;i>=0;--i)for(intj=n-1;j>=0;--j){dp[i][j]=min(dp[i][j+1],dp[i+1][j])-d[i][j];dp[i][j]=max(1,dp[i][j]);}// 4. 返回值returndp[0][0];}};