题解 | #最长上升子序列(一)#

直接dfs+动态规划解决

#include<iostream>
#include<cstring>
using namespace std;
int graph[100][100],dp[100][100];
void dfs(int n,int m,int row,int col){
    //右
    if(col + 1 < m && graph[row][col + 1] < graph[row][col]){
        dfs(n,m,row,col + 1);
        dp[row][col] = max(dp[row][col + 1] + 1,dp[row][col]);
    }
    //下
    if(row + 1 < n && graph[row + 1][col] < graph[row][col]){
        dfs(n,m,row + 1,col);
        dp[row][col] = max(dp[row + 1][col] + 1,dp[row][col]);
    }
    //左
    if(col - 1 >= 0 && graph[row][col - 1] < graph[row][col]){
        dfs(n,m,row,col - 1);
        dp[row][col] = max(dp[row][col - 1] + 1,dp[row][col]);
    }
    //上
    if(row - 1 >= 0 && graph[row - 1][col] < graph[row][col]){
        dfs(n,m,row - 1,col);
        dp[row][col] = max(dp[row - 1][col] + 1,dp[row][col]);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m,ans = 0;
    cin >> n >> m;
    for(int i = 0;i < n;++i)
        for(int j = 0;j < m;++j){
            cin >> graph[i][j];
            dp[i][j] = 1;
        }
    for(int i = 0;i < n;++i)
        for(int j = 0;j < m;++j){
            dfs(n,m,i,j);
            ans = max(ans,dp[i][j]);
        }
    cout << ans;
}