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)
写一个方便的函数：

int va(int i,int j,int k){
   if(i <= 0 || j <= 0 || k <= 0)   return 1;
  return a[i][j][k];
}

java 代码

可以减少不少判断。
自底向上求解：

  cpp 代码:
void computeW(){
    int i,j,k;

    for(i = 1; i < 21; i++)
        for(j = 1; j < 21; j++)
            for(k = 1; k < 21; k++){
                if(i < j && j < k)
                    a[i][j][k] = va(i,j,k-1) + va(i,j-1,k-1) - va(i,j-1,k);
                else
                    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);
            }
}

都计算完了，输入什么就返回什么吧：

java 代码

int w(int i,int j,int k){
   if(i <= 0 || j <= 0 || k <= 0)
      return 1;
  if(i > 20 || j > 20 || k > 20)
      return a[20][20][20];
  else
      return a[i][j][k];
}

完整的代码：
cpp 代码
#include<iostream></iostream>
using namespace std;

int a[21][21][21];
int va(int i,int j,int k){
  if(i <= 0 || j <= 0 || k <= 0)
      return 1;
  return a[i][j][k];
}
void computeW(){
    int i,j,k;

    for(i = 1; i < 21; i++)
        for(j = 1; j < 21; j++)
            for(k = 1; k < 21; k++){
                if(i < j && j < k)
                    a[i][j][k] = va(i,j,k-1) + va(i,j-1,k-1) - va(i,j-1,k);
                else
                    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);
            }
}
int w(int i,int j,int k){
   if(i <= 0 || j <= 0 || k <= 0)
      return 1;
  if(i > 20 || j > 20 || k > 20)
      return a[20][20][20];
  else
      return a[i][j][k];
}
int main(){
    int i,j,k;
    computeW();
    while(cin>>i>>j>>k){
      if(i==-1 && j==-1 && k==-1)
          break;
      cout << "w(" << i << ", " << j << ", " << k <<")" <<" = " << w(i,j,k) << endl;
    }
    return 0;
}

分享到：

搜索引擎Nutch源代码研究之一 网页抓取(4 ... | Square Coins一个DP问题分析

• 2007-12-17 20:39
• 浏览 2663
• 评论(0)
• 查看更多