C 解法, 执行用时: 3ms, 内存消耗: 400KB, 提交时间: 2022-02-20

#include<stdio.h>
int n,m;
int a[102][102]={0};
int dp[102][102]={0};
int b[4]={-1,0,1,0};
int c[4]={0,1,0,-1};
int maxb(int a,int b)
{
    if(a>b)
        return a;
        else
            return b;
}
int w(int x,int y)
{
    if(dp[x][y]!=0)//重复不计算
        return dp[x][y];
    int t=1;
    for(int i=0;i<4;i++)
    {
        int dx=x+b[i];
        int dy=y+c[i];
        if(dx>0 && dx<=n && dy>0 && dy<=m && a[dx][dy]<a[x][y])
        {
            t=maxb(w(dx,dy)+1,t);
        }
    }
    return dp[x][y]=t;
}
int main()
{
    int maxa=0;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            maxa=maxb(w(i,j),maxa);
        }
    }
    printf("%d",maxa);
}

C 解法, 执行用时: 4ms, 内存消耗: 384KB, 提交时间: 2022-05-08

#include<stdio.h>
int n, m, a[102][102] = {0}, f[102][102] = {0}, b[4] = {-1, 0, 1, 0}, c[4] = {0, 1, 0, -1};
int maxb(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}
int w(int x, int y) {
    if (f[x][y] != 0)
        return f[x][y];
    int t = 1;
    for (int i = 0; i < 4; i++) {
        int dx = x + b[i];
        int dy = y + c[i];
        if (dx > 0 && dx <= n && dy > 0 && dy <= m && a[dx][dy] < a[x][y]) {
            t = maxb(w(dx, dy) + 1, t);
        }
    }
    return f[x][y] = t;
}
int main() {
    int maxa = 0;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            maxa = maxb(w(i, j), maxa);
        }
    }
    printf("%d", maxa);
}

C 解法, 执行用时: 4ms, 内存消耗: 396KB, 提交时间: 2022-06-21

#include <stdio.h>
#include <stdbool.h>

void dfs(int i, int j, int **dp, int **map, int n, int m) {
    int maxDp = 0;
    if (i > 0) {
        if (map[i-1][j] < map[i][j]) {
            if (dp[i-1][j] == 0) {
                dfs(i-1, j, dp, map, n, m);   
            }
            
            if (dp[i-1][j] > maxDp) {
                maxDp = dp[i-1][j];
            }
        }
    }
    if (j > 0) {
        if (map[i][j-1] < map[i][j]) {
            if (dp[i][j-1] == 0) {
                dfs(i, j-1, dp, map, n, m);
            }
            
            if (dp[i][j-1] > maxDp) {
                maxDp = dp[i][j-1];
            }
        }
    }
    if (i < n-1) {
        if (map[i+1][j] < map[i][j]) {
            if (dp[i+1][j] == 0) {
                dfs(i+1, j, dp, map, n, m);
            }
            
            if (dp[i+1][j] > maxDp) {
                maxDp = dp[i+1][j];
            }
        }
    }
    if (j < m-1) {
        if (map[i][j+1] < map[i][j]) {
            if (dp[i][j+1] == 0) {
                dfs(i, j+1, dp, map, n, m);
            }
            
            if (dp[i][j+1] > maxDp) {
                maxDp = dp[i][j+1];
            }
        }
    }
    
    dp[i][j] = maxDp + 1;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    int **map = (int **)malloc(sizeof(int *) * n);
    for (int i = 0; i < n; i++) {
        map[i] = (int *)malloc(sizeof(int) * m);
        
        for (int j = 0; j < m; j++) {
            scanf("%d", &map[i][j]);
        }
    }
    
    int **dp = (int **)malloc(sizeof(int *) * n);
    for (int i = 0; i < n; i++) {
        dp[i] = (int *)malloc(sizeof(int) * m);
        memset(dp[i], 0, sizeof(int) * m);
    }
    
    int maxLen = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (dp[i][j] == 0) {
                dfs(i, j, dp, map, n, m);
            }
            if (dp[i][j] > maxLen) {
                maxLen = dp[i][j];
            }
        }
    }
    
    printf("%d", maxLen);
    
    for (int i = 0; i < n; i++) {
        free(map[i]);
        free(dp[i]);
    }
    free(map);
    free(dp);
    
    return 0;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 452KB, 提交时间: 2022-02-15

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int f[105][105], a[105][105], n, m;
int X[4] = {-1, 1, 0, 0}, Y[4] = {0, 0, 1, -1};
int dfs(int x, int y)
{
	if (f[x][y]) return f[x][y];
	int ttt = 1;
	for (int i = 0; i < 4; ++i)
	{
		int dx = x + X[i], dy = y + Y[i];
		if (dx >= 1 && dx <= n && dy >= 1 && dy <= m && a[dx][dy] < a[x][y]) 
		{
			ttt = max(ttt, 1 + dfs(dx, dy));	
		}
	}
	return f[x][y] = ttt;
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			scanf("%d", &a[i][j]);
		}
	}
	int MAX = 0;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			MAX = max(MAX, dfs(i, j));
		}
	}
	printf("%d", MAX);
	return 0;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 512KB, 提交时间: 2022-03-22

#include"iostream"
using namespace std;
int n,m;
int map[105][105];
int f[105][105];//以(i,j)为起点的最长递增路径长度
int dx[4] ={-1,0,1,0};
int dy[4]={0,1,0,-1};

int dfs(int x,int y)
{
    if(f[x][y]) return f[x][y];
    int len = 1;
    for(int i =0;i<4;i++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&map[x][y]<map[nx][ny]) len = max(len,dfs(nx,ny)+1);
    }
    f[x][y] = len;
    return len;
}

int main()
{
    ios::sync_with_stdio(false);
    int res = 0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>map[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            f[i][j] = dfs(i,j);
            res = max(res,f[i][j]);
        }
    }
    cout<<res;
    return 0;
}