Javaでの階段の登り方の問題と解決法

この問題は、動的プログラミングの一種であるメモ化再帰を使って効率的に解くことができます。以下に、いくつかの方法とそれぞれのコード例を紹介します。

メモ化再帰を使った解法:

import java.util.HashMap;
import java.util.Map;
public class StairClimbing {
    public static int climbStairs(int n) {
        Map<Integer, Integer> memo = new HashMap<>();
        return climbStairsHelper(n, memo);
    }
    private static int climbStairsHelper(int n, Map<Integer, Integer> memo) {
        if (n <= 2) {
            return n;
        }

        if (memo.containsKey(n)) {
            return memo.get(n);
        }

        int ways = climbStairsHelper(n - 1, memo) + climbStairsHelper(n - 2, memo);
        memo.put(n, ways);

        return ways;
    }
    public static void main(String[] args) {
        int n = 3;
        int totalWays = climbStairs(n);
        System.out.println("Total ways to climb the stairs: " + totalWays);
    }
}

動的計画法（DP）を使った解法:

public class StairClimbing {
    public static int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }

        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
    public static void main(String[] args) {
        int n = 3;
        int totalWays = climbStairs(n);
        System.out.println("Total ways to climb the stairs: " + totalWays);
    }
}

以上が、Javaでの階段の登り方の問題を解くためのいくつかの方法とコード例です。これらのアルゴリズムを使うと、与えられた階段の数に対して効率的に解を求めることができます。ぜひ試してみてください！