题意

给一个n×n的矩阵，老鼠从（1,1）出发

，

老鼠每次最多走k步停下来，停下的这个位置只能比上一个停留的位置大，并获取其价值，每次只能水平或垂直走，问从（0,0）出发最大能得到的价值

分析

错误思路：dp[i][j]， 以dp[i][j]结尾的最大价值，这样状态不好转移

正解：直接根据题意

定义：dp[i][j] : 从（i，j）出发的可以获得的最大价值，直接找到从（i，j）出发可以到达的最大价值

转移：根据题意直接转移即可

#include 
       
        #define ll long longusing namespace std;const int maxn = 1e5 + 10;\ int xxx[4]={-1,1,0,0}; int yyy[4]={
     0,0,-1,1};int n,k;int dp[105][105];int a[105][105];int dfs(int x,int y){    if(dp[x][y]>0)        return dp[x][y];    dp[x][y] = a[x][y];    for(int i = 1; i <= k; i++)    {        for(int j = 0; j < 4; j++)        {            int xx = x + i*xxx[j];            int yy = y + i*yyy[j];            if(xx>=1 && xx<=n && yy>=1 && yy<=n && a[xx][yy] > a[x][y])            {                dp[x][y]=max(dp[x][y], dfs(xx,yy)+a[x][y]);            }        }    }    return dp[x][y];}int main(){    while(scanf("%d%d", &n, &k)!=EOF)    {        if(n==-1)            break;        for(int i = 1; i <= n; i++)        {            for(int j = 1; j <= n; j++)            {                scanf("%d", &a[i][j]);            }        }        memset(dp,0,sizeof(dp));        dfs(1,1);        printf("%d\n", dp[1][1]);    }    return 0;}