Java实现记忆化搜索

曾经终败给现在 2022-06-01 13:49 200阅读 0赞

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

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

题目描述

对于一个递归函数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];
        }
    }