巧用记忆化搜索代替暴力递归（洛谷P1464题题解，Java语言描述）

题目要求

P1464题目链接

分析

如果……你信了这题干，真的写了递归……TLE警告！！！

所以，就需要优化嘛……

[−9223372036854775808,9223372036854775807]这个范围，就是C的longlong / Java的long诶，算是一种数很大但还有良心的提示吧。

这题比较适合记忆化搜索，这也是我第一次写记忆化搜索的题解诶，就扯一扯……

一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。这种方法综合了搜索和动态规划两方面的优点，因而还是很有实用价值的。

对于本题的话，只要一个记忆化储存就可以避免大量运算量（大佬们都说这玩意和递推/动态规划差不多）。 主要思路就是开一个三维数组，把每一个“w”函数的值储存起来，下一次就可以直接调用，节省大量时间。

使用的时候还要先想，记忆化的数组要开多大。对于这个题来说，输入数据在long（Java）范围内，对于每一组a，b，c都使用一个变量来进行记忆化是不现实的。 但是，根据题意，当a20时，返回值都是w(20,20,20)，因此，对于以上的这些数据，我们可以不进行记忆化处理。 所以， long[25][25][25] 就可以了……

输出注意空格！！！我因此白白WA一次，真悲催啊~~

AC代码（Java语言描述）

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    private static long[][][] array = new long[25][25][25];

    private static long w(int a, int b, int c) {
        if(a  20) {
            return w(20, 20, 20);
        }
        if(a