LIS 2D (Skiing)

DP:

DP[i][j] = max(DP[i-1][j],DP[i+1][j],DP[i][j-1],DP[i][j+1]) + 1

if map[i][j] > map[x][y] && (x,y) in the map

#include<iostream>  
using namespace std;  
const int Max = 105;  

int row, col;  
int map[Max][Max];                           //  记录c++图各点的高度。  
int dp[Max][Max];                            //  记录以各点为起点的最长下降路径的长度。  

int dfs(int r, int c)  
{  
    if(dp[r][c] != 0)    
        return dp[r][c];      //  若dp[r][c]不为0，则表示它已被访问。  
    int max = 1;  
    if(r + 1 <= row && map[r][c] > map[r + 1][c])  
    {  
        int len = dfs(r + 1, c) + 1;  
        if(len > max)   
            max = len;  
    }  
    if(r - 1 >= 1 && map[r][c] > map[r - 1][c])  
    {  
        int len = dfs(r - 1, c) + 1;  
        if(len > max)    
            max = len;  
    }  
    if(c + 1 <= col && map[r][c] > map[r][c + 1])  
    {  
        int len = dfs(r, c + 1) + 1;  
        if(len > max)    
            max = len;  
    }  
    if(c - 1 >= 1 && map[r][c] > map[r][c - 1])  
    {  
        int len = dfs(r, c - 1) + 1;  
        if(len > max)    
            max = len;  
    }  
    return map[r][c] = max;   
}  

int main()  
{  
    int i, j;  
    cin >> row >> col;  
    for(i = 1; i <= row; i ++)  
        for(j = 1; j <= col; j ++)  
            cin >> map[i][j];  
        int ans = 0;  
        memset(dp, 0, sizeof(dp));  
        for(i = 1; i <= row; i ++)  
            for(j = 1; j <= col; j ++)  
            {  
                dp[i][j] = dfs(i, j);  //  用记忆化搜索求出dp[i][j]，同时也求出了其路径上的dp[x][y]。  
                if(dp[i][j] > ans)  
                    ans = dp[i][j];  
            }  
            cout << ans << endl;  
            return 0;  
}

Sort + DP

Set a dp matrix that each elements in it is 1 at first.

Then put the matrix into a M x N array (Structure is Point (x, y, height)). Sort the array by height and loop once from high to low. In each point, get its 4 around points:

if(point[i][j] > point[i - 1][j] && dp[i - 1][j] < dp[i][j] + 1)
    dp[i - 1][j] = dp[i][j] + 1;

if(point[i][j] > point[i][j - 1] && dp[i][j - 1] < dp[i][j] + 1)
    dp[i][j - 1] = dp[i][j] + 1;

if(point[i][j] > point[i + 1][j] && dp[i + 1][j] < dp[i][j] + 1)
    dp[i + 1][j] = dp[i][j] + 1;

if(point[i][j] > point[i][j + 1] && dp[i][j + 1] < dp[i][j] + 1)
    dp[i][j + 1] = dp[i][j] + 1;

Then loop the dp matrix once and find the max value.