题意分析
在一个范围为N×NN \times NN×N的矩阵当中去求解如何从Sx,SyS_x,S_ySx ,Sy 前往终点[N,N][N,N][N,N]。 在这个矩阵当中会存在多种情况，一开始价值为TTT。
* 前往的坐标系所指向的类别为. ，价值-1。
* 前往的坐标系所指向的类别为M，价值-k
* 前往的坐标系所指向的类别为D，价值+z
针对于起点的类别不同采取
* 出现D的话进行+z的操作
方向只有右下
算法解析
根据前往的方向可以快速的求得状态和最基本的转移方程
设定dp[i][j]dp[i][j]dp[i][j]为到达坐标[i,j][i,j][i,j]的最大价值。
到达点dp[i][j]dp[i][j]dp[i][j]只能由上和左来到，也就是dp[i][j]=max(dp[i−1][j],dp[i][j−1])dp[i][j] = max(dp[i-1][j],dp[i][j-1])dp[i][j]=max(dp[i−1][j],dp[i][j−1])
然后，根据地图上的三种情况,MD来对于dp进行累加或者减少。
IFIFIF mp[i][j]=.mp[i][j] = .mp[i][j]=. dp[i][j]=max(dp[i−1][j],dp[i][j−1])−1dp[i][j] = max(dp[i-1][j],dp[i][j-1]) - 1dp[i][j]=max(dp[i−1][j],dp[i][j−1])−1
IFIFIF mp[i][j]=Dmp[i][j] = Dmp[i][j]=D dp[i][j]=max(dp[i−1][j],dp[i][j−1])+zdp[i][j] = max(dp[i-1][j],dp[i][j-1]) + zdp[i][j]=max(dp[i−1][j],dp[i][j−1])+z
IFIFIF mp[i][j]=***[i][j] = ***[i][j]=M dp[i][j]=max(dp[i−1][j],dp[i][j−1])−kdp[i][j] = max(dp[i-1][j],dp[i][j-1]) - kdp[i][j]=max(dp[i−1][j],dp[i][j−1])−k
我们设定dp[Sx][Sy]dp[S_x][S_y]dp[Sx ][Sy ]为初始状态，价值一开始为T，但是一旦Mp[Sx][Sy]=DMp[S_x][S_y] = DMp[Sx ][Sy ]=D ，总价值需要加上z进行。
针对于状态转移方程书写代码即可。
时间复杂度分析
最坏需要遍历整个矩阵，所以时间复杂度为O(n2)O(n^2)O(n2)
STD标程
