题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2859

思路：

第一次碰到这种矩阵上的DP题，想了半天也没想明白。本来想用子矩阵的左上角坐标和右下角坐标当作状态，但这样内存肯定是不够的。后来网上查了就明白了。

用dp[i][j]表示以(i,j)为左下角的矩阵的维数最大值，然后在斜边上DP，建立dp[i][j]与dp[i-1][j+1]的联系。具体思路见代码，仔细想想就明白了。也学到关于矩阵的题目多考虑对角线。我在这wa了一发，原因是我将res初始化为0，而如果输入数据是n=1（即一维），结果应该是1，而我的程序结果是0，把res初始化为1就行了，以后要多注意特殊情况。

1 #include
     
       2 using namespace std; 3  4 int n,res,dp[1005][1005]; 5 char a[1005][1005]; 6  7 int main(){ 8     while(~scanf("%d",&n),n){ 9         res=1;10         for(int i=0;i
      
       =0&&tj
       
        =dp[i-1][j+1]+1) dp[i][j]=dp[i-1][j+1]+1;23                 else dp[i][j]=t;24                 if(dp[i][j]>res) res=dp[i][j];25             }26         printf("%d\n",res);27     }28     return 0;29 }