动态规划学习之地牢游戏

动态规划学习之地牢游戏

题目：
从左下角到右下角，生命值至少为多少，才可以保证骑士在行走的过程中至少保持生命值为1(只能向下或者向右走)

关键是每一步都要至少生命值为1。
所以并不是简单的怎么走的路径和最大
我只知道题目，不知道具体输入输出的要求，有没有说机试试有没有AC，只是过了样列，如果有人试了，求告诉我一下是不是有什么bug或者对了，谢谢！
思路：
定义dp[i][j][1]与dp[i][j][2]分别代表（i，j）位置的最小初始生命值与目前生命值的状态；
再分别定义k1，p1代表从来上面到(i,j)的应该有的最小初始生命值与目前生命值的状态；
k2,p2代表从左边到(i,j)的应该有的最小初始生命值与目前生命值的状态；
动态方程：最后取dp[i][j][1]=min(k1,k2);dp[i][j][2]=对应的p1或者p2；
具体的已经在注释中有了

//*题目：
//*从左下角到右下角，生命值至少为多少，才可以保证骑士在行走的过程中至少保持生命值为1
//*关键是每一步都要至少生命值为1
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <math.h>
using namespace std;
//todo 动态规划之地牢游戏
#define maxn 101
int main()
{int dp[maxn][maxn][3];int map[maxn][maxn];int n;scanf("%d", &n);for (int i = 1; i <= n; i++) //*输入地图{for (int j = 1; j <= n; j++){scanf("%d", &map[i][j]);}}dp[1][1][1] = map[1][1] >= 0 ? 1