地图路线[dp]

1.摘花生

Hello Kitty想摘点花生送给她喜欢的米老鼠。

她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。

地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。

Hello Kitty只能向东或向南走，不能向西或向北走。

问Hello Kitty最多能够摘到多少颗花生。

花生.png

• 思路：左上->右下，每一步向右或向下，则每个点只能从上或左边来，即每个点的值加上max(上,左)即可。

    for(int i = 1; i <= r; i++)//从1开始初始化则不需要考虑边界
        for(int j = 1; j <= c; j++)
            cin >> m[i][j];
        for(int i = 1; i <= r; i++)
            for(int j = 1; j <= c; j++)
                dp[i][j] = m[i][j] + 
                max(dp[i-1][j], dp[i][j-1]);
  

2.地下城

一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快到达公主，骑士决定每次只向右或向下移动一步。\

• 思路：两题类似，将2题翻转，则由P->K，所剩余健康点最多？即消耗最小，min(下,右)-每个点的值;--但是，骑士不能死，每一步都要保证骑士活着！

    dp[m-1][n] = 1, dp[m][n-1] = 1;
        for(int i = m-1; i >= 0; --i)
            for(int j = n-1; j >= 0; --j)
                dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]);
                //生命值最小为1,保证骑士活着。