Java实现记忆化搜索

记忆化搜索
是在使用递归搜索或者类似的情况下
使用一般的递归或许需要太多的时间与内存
这时我们就可以使用记忆化搜索

其本质为在递归搜索中
如果遇到了没有搜索过的
进行搜索并在内存中记录结果
如果之前搜索过
就直接调用结果

题目描述

对于一个递归函数w(a,b,c)

如果a<=0 or b<=0 or c<=0就返回值1.

如果a>20 or b>20 or c>20就返回w(20,20,20)

如果a< b并且b< c 就返回w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)

其它别的情况就返回w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)

这是个简单的递归函数，但实现起来可能会有些问题。当a,b,c均为15时，调用的次数将非常的多。你要想个办法才行.

/*

absi2011 : 比如 w(30,-1,0)既满足条件1又满足条件2

这种时候我们就按最上面的条件来算

所以答案为1

*/

输入输出格式

输入格式：
会有若干行.

并以-1，-1，-1结束.

保证输入的数在-9223372036854775808~9223372036854775807之间

并且是整数

输出格式：
输出若干行

格式:

[b]w(a,b,_c)=你的输出(代表空格)[/b]

public static void main(String[] args) {
// TODO Auto-generated method stub

Scanner scanner = new Scanner(System.in);
for(int i=0; i<25; i++) {
    for(int j=0; j<25; j++) {
        for(int k=0; k<25; k++) {
            ww[i][j][k] = 0;
        }
    }
}
while(true) {
    int a = scanner.nextInt();
    int b = scanner.nextInt();
    int c = scanner.nextInt();
    if(a == -1 && b == -1 && c == -1) {
        break;
    }else {
        System.out.println("w(" + a + ", " + b + ", " + c + ") = " + w(a, b, c));
    }
}
scanner.close();

}

private static int[][][] ww= new int[25][25][25];

public static int w(long a, long b, long c) {

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

}