题解 | 【模板】记忆化搜索

import java.io.*;
import java.util.*;

public class Main {
    private static final int MOD = 1000000007;
    private static long[][][] memory = new long[101][101][101];

    public static void main(String[] args) throws IOException {

        // 使用BufferedReader读取输入，使用PrintWriter输出结果
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));


        int T = Integer.parseInt(br.readLine().trim());

        while (T-- > 0) {
            String[] s = br.readLine().trim().split("\\s+");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            int c = Integer.parseInt(s[2]);
            out.println(solve(a, b, c));
        }


        // 刷新输出流，确保所有输出都被写入
        out.flush();
        // 关闭输出流，释放资源
        out.close();
        // 关闭输入流，释放资源
        br.close();
    }

    /**
     * 这是一个递归求解函数，使用记忆化技术来优化性能
     *
     * @param a 第一个参数
     * @param b 第二个参数
     * @param c 第三个参数
     * @return 返回计算结果，类型为long
     */
    private static long solve(int a, int b, int c) {
        // 如果任一参数小于等于0，返回1
        if (a <= 0 || b <= 0 || c <= 0) {
            return 1;
        }

        // 如果结果已经计算过并存储在memory中，直接返回存储的结果
        if (memory[a][b][c] != 0) {
            return memory[a][b][c];
        }

        long res; // 用于存储计算结果

        // 当a<b且b<c时，使用特定的递归公式计算
        if (a < b && b < c) {
            res = (solve(a, b, c - 1) + solve(a, b - 1, c - 1)) % MOD;
            res = (res - solve(a, b - 1, c) + MOD) % MOD;
        } else {
            res = (solve(a - 1, b, c) + solve(a - 1, b - 1, c)) % MOD;
            res = (res + solve(a - 1, b, c - 1)) % MOD;
            res = (res - solve(a - 1, b - 1, c - 1) + MOD) % MOD;
        }
        return memory[a][b][c] = res;
    }
}