POJ 1579 (DP)

题目：http://poj.org/problem?id=1579

题目说递归很费时，怎么办？

递归费时的一个很重要的原因就是很多子问题重复计算了，如果计算过的子问题保存下来，用时直接取来用。就是具备记忆能力的递归了，那样就比较快了。

状态转移方程就是题目的递归式了。

代码：

#include <stdio.h>
#include <string.h>
#define N 21
 
int ans[N][N][N];
int dp(int a,int b,int c);
 
int main()
{
   int a,b,c;
   
     while( ~scanf("%d%d%d",&a,&b,&c) )
     {
       if(-1 ==a && -1 == b && -1 ==c ) break;
       memset(ans,-1,sizeof(ans));
       printf("w(%d, %d, %d) = %d\n",a,b,c,dp(a,b,c));
     } 
   return 0;    
} 

int dp(int a,int b,int c)
{
    if( a<=0 || b<=0 || c<=0) return 1;
    if(a>20 || b>20 || c> 20) 
    {
         if(-1 == ans[20][20][20] )          
           ans[20][20][20] = dp(20,20,20);
         return ans[20][20][20];
    }
    
    if(a<b && b<c)
    {
        if(-1 == ans[a][b][c-1]) ans[a][b][c-1] = dp(a,b,c-1);   
        if(-1 == ans[a][b-1][c-1]) ans[a][b-1][c-1] = dp(a,b-1,c-1);            
        if(-1 == ans[a][b-1][c]) ans[a][b-1][c] = dp(a,b-1,c);               
        ans[a][b][c] = ans[a][b][c-1] + ans[a][b-1][c-1]- ans[a][b-1][c];
    }
    else
    {
        if(-1 == ans[a-1][b][c]) ans[a-1][b][c] = dp(a-1,b,c);
        if(-1 == ans[a-1][b-1][c])  ans[a-1][b-1][c] = dp(a-1,b-1,c);            
        if(-1 == ans[a-1][b][c-1])  ans[a-1][b][c-1] = dp(a-1,b,c-1);            
        if(-1 == ans[a-1][b-1][c-1])  ans[a-1][b-1][c-1] = dp(a-1,b-1,c-1);               
        ans[a][b][c] = ans[a-1][b][c]+ans[a-1][b-1][c]+ans[a-1][b][c-1]-ans[a-1][b-1][c-1];
    }
    return ans[a][b][c];
}