8636 跳格子 SCAU新生赛 {纯动态规划做法}_跳格子 动态规划

8636 跳格子
看到也有人写过这道题题解，不过使用搜索+记忆化的，我这里提供一个纯动态规划的思路。
1.确定状态，首先，它肯定跳到了最后一列格子上，至于哪个格子我先不管。
2.那么它是怎么跳过来的呢？它是通过距离它根号k的范围内跳过来的，那我要使得我最后跳下去是最大的，那我我就要这个范围里面选一个最大的，这样
我的状态转移方程就是dp[i][j]=max(范围内dp[][]最大值)+a[i][j]。
3.最后再遍历一遍最后一列，选最大的就好了

#include <stdio.h>
#include <math.h>
#include <limits.h>
#define MAXN 10000+500
 long long dp[MAXN][MAXN];
 long long a[MAXN][MAXN];
int main()
{
   
    int kase;
    scanf("%d",&kase);
    while(kase--)
    {
   
        int n, m;
        scanf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15