【动态规划】地下城游戏

题目链接https://leetcode.cn/problems/dungeon-game/description/classSolution{public:intcalculateMinimumHP(vectorvectorintd){/*时空复杂度O(mn)*/intmd.size(),nd[0].size();// 1. 创建dp表vectorvectorintdp(m1,vectorint(n1,INT_MAX));// 2. 初始化dp[m-1][n]dp[m][n-1]1;// 3. 填表for(intim-1;i0;--i)for(intjn-1;j0;--j){dp[i][j]min(dp[i][j1],dp[i1][j])-d[i][j];dp[i][j]max(1,dp[i][j]);}// 4. 返回值returndp[0][0];}};