dp思想：每个最优解都和子最优解有关，数组存储每个步骤的解
dfs：遍历方法的改变，输入数据是不规则的，不能按照之前的dp思路访问，而是类似于图的遍历
#include<iostream> #include<stdio.h> using namespace std; int a[100][100] = {0}; int dp[100][100] = {0}; int dx[4] = {-1,0,0,1}; int dy[4] = {0,-1,1,0}; int n,m; bool isIn(int x,int y) { if(x>=0 && x<n && y>=0 && y<m) return true; return false; } int DFS(int x,int y) { if(dp[x][y]) return dp[x][y]; int tmp; int max = 1; for(int i =0;i<4;++i) { if(isIn(x+dx[i],y+dy[i]) && a[x][y] > a[x+dx[i]][y+dy[i]] ) { tmp = 1+DFS(x+dx[i],y+dy[i]); if(dp[x][y]<tmp) dp[x][y] = tmp; } } if(dp[x][y]<max) dp[x][y] = max; return dp[x][y]; } int main() { int maxlen,tmpway; bool bway = false; while(scanf("%d%d",&n,&m) != EOF) { maxlen = 0; for(int i =0;i<n;++i) { for(int j =0;j<m;++j) { scanf("%d",&a[i][j]); } } for(int i =0;i<n;++i) { for(int j =0;j<m;++j) { int tmp = DFS(i,j); if(maxlen <tmp) maxlen = tmp; } } printf("%d\n",maxlen); } return 0; }
