JAVA的动态规划解法

解题思路:

注意事项:

参考代码:

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int[][] dp = new int[n + 1][n + 1];
        countPaths(n, 1, dp);
        System.out.println(dp[n][1]+1);
    }
    static int countPaths(int a, int b, int[][] dp) {
        if (dp[a][b] != 0) {
            return dp[a][b]; // 如果已经计算过，直接返回结果
        }
        if (a / 2 < b) {
            return 0; // 不满足条件，返回0
        }
        int count = 1; // 至少有一个数（当前数）
        count += countPaths(a, b + 1, dp); // 递归调用1
        count += countPaths(b, 1, dp); // 递归调用2
        dp[a][b] = count; // 存储结果
        return count;
    }
}