2007-12-17

Function Run Fun一个简单的DP问题分析

关键字: 动态规划

问题:

We all love recursion! Don't we?

Consider a three-parameter recursive function w(a, b, c):

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
1

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
w(20, 20, 20)

if a < b and b < c, then w(a, b, c) returns:
w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns:
w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

This is an easy function to implement. The problem is, if implemented directly, for moderate values of a, b and c (for example, a = 15, b = 15, c = 15), the program takes hours to run because of the massive recursion.


Input

The input for your program will be a series of integer triples, one per line, until the end-of-file flag of -1 -1 -1. Using the above technique, you are to calculate w(a, b, c) efficiently and print the result. For example:
1 1 1
2 2 2
10 4 6
50 50 50
-1 7 18
-1 -1 -1

Output

Print the value for w(a,b,c) for each triple, like this: 
w(1, 1, 1) = 2
w(2, 2, 2) = 4
w(10, 4, 6) = 523
w(50, 50, 50) = 1048576
w(-1, 7, 18) = 1

分析:
这个问题直接递归写，效率相当低，当 a = 15, b = 15, c = 15，就得运行好几个小时才能出来结果。
这个问题其实应该是最简单的一种动态规划题目了，因为递推式已经给出了。而动态规划的难点
在于构造出递推式。当时熟悉用程序求解递推式，也是动态规划的三个步骤之一（最优解结
构分析、构造递推式、自底向上求解递推式[也可以递归的lookup式的]）
此题只需要从底向上求解下面递推式就行：
w(a,b,c) = if a <= 0 or b <= 0 or c <= 0 return 1;
           else if a > 20 or b > 20 or c > 20  return w(20, 20, 20);
           else if a < b and b < c, then w(a, b, c) w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
           else return w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
写一个方便的函数：
  1. int va(int i,int j,int k){     
  2.    if(i <= 0 || j <= 0 || k <= 0)   return 1;     
  3.   return a[i][j][k];   
  4. }  
java 代码


可以减少不少判断。
自底向上求解：
  cpp 代码:
  1. void computeW(){    
  2.     int i,j,k;    
  3.         
  4.     for(i = 1; i < 21; i++)    
  5.         for(j = 1; j < 21; j++)    
  6.             for(k = 1; k < 21; k++){    
  7.                 if(i < j && j < k)    
  8.                     a[i][j][k] = va(i,j,k-1) + va(i,j-1,k-1) - va(i,j-1,k);    
  9.                 else   
  10.                     a[i][j][k] = va(i-1,j,k) + va(i-1,j-1,k) + va(i-1,j,k-1) - va(i-1,j-1,k-1);     
  11.             }    
  12. }   
都计算完了，输入什么就返回什么吧：
java 代码
  1. int w(int i,int j,int k){   
  2.    if(i <= 0 || j <= 0 || k <= 0)   
  3.       return 1;   
  4.   if(i > 20 || j > 20 || k > 20)   
  5.       return a[20][20][20];   
  6.   else  
  7.       return a[i][j][k];   
  8. }  


完整的代码：
cpp 代码
  1. #include   
  2. using namespace std;   
  3.   
  4. int a[21][21][21];   
  5. int va(int i,int j,int k){   
  6.   if(i <= 0 || j <= 0 || k <= 0)   
  7.       return 1;   
  8.   return a[i][j][k];   
  9. }   
  10. void computeW(){   
  11.     int i,j,k;   
  12.        
  13.     for(i = 1; i < 21; i++)   
  14.         for(j = 1; j < 21; j++)   
  15.             for(k = 1; k < 21; k++){   
  16.                 if(i < j && j < k)   
  17.                     a[i][j][k] = va(i,j,k-1) + va(i,j-1,k-1) - va(i,j-1,k);   
  18.                 else  
  19.                     a[i][j][k] = va(i-1,j,k) + va(i-1,j-1,k) + va(i-1,j,k-1) - va(i-1,j-1,k-1);    
  20.             }   
  21. }   
  22. int w(int i,int j,int k){   
  23.    if(i <= 0 || j <= 0 || k <= 0)   
  24.       return 1;   
  25.   if(i > 20 || j > 20 || k > 20)   
  26.       return a[20][20][20];   
  27.   else  
  28.       return a[i][j][k];   
  29. }   
  30. int main(){   
  31.     int i,j,k;   
  32.     computeW();   
  33.     while(cin>>i>>j>>k){   
  34.       if(i==-1 && j==-1 && k==-1)   
  35.           break;   
  36.       cout << "w(" << i << ", " << j << ", " << k <<")" <<" = " << w(i,j,k) << endl;   
  37.     }   
  38.     return 0;   
  39. }   


评论
发表评论

您还没有登录，请登录后发表评论

fuliang
搜索本博客
我的相册
7633f7ab-e7a9-3fa7-ab0d-919030af4eda-thumb
cooliris
共 9 张
存档
最新评论