動的プログラミング問題へのアプローチ

動的プログラミング問題を解決するための5つのステップ：

1. DP配列（DPテーブル）とそのインデックスの意味を定義する
2. 漸化式を決定する
3. DP配列の初期化方法を決定する（配列オーバーフローに注意）
4. 計算順序を決定する
5. DP配列の具体例を導出する

フィボナッチ数

フィボナッチ数列（通常 F(n) で表される）は、0 と 1 から始まり、その後の各数値が前の2つの数値の和となる数列です。つまり：

F(0) = 0、F(1) = 1
F(n) = F(n - 1) + F(n - 2)、ただし n > 1

n が与えられたとき、F(n) を計算してください。

例 1：

入力：n = 2
出力：1
説明：F(2) = F(1) + F(0) = 1 + 0 = 1

考え方：

1. DP配列とそのインデックスの意味を定義する

dp[i] はフィボナッチ数列のi番目の数を表す

2. 漸化式を決定する

F(n) = F(n - 1) + F(n - 2)

3. DP配列の初期化方法を決定する

F(0) = 0、F(1) = 1

4. 計算順序を決定する

漸化式 dp[i] = dp[i - 1] + dp[i - 2] から、dp[i] は dp[i - 1] と dp[i - 2] に依存するため、計算順序は前から後ろへとなる

5. DP配列の具体例を導出する

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55........

コード：

class Solution {
    public int fibonacci(int n) {
        if (n <= 1) return n; // nが1以下の場合、配列オーバーフローを防ぐため
        int[] sequence = new int[n + 1];
        sequence[0] = 0;
        sequence[1] = 1;
        for (int i = 2; i <= n; i++) {
            sequence[i] = sequence[i - 1] + sequence[i - 2];
        }
        return sequence[n];
    }
}

階段の登り方

あなたが階段を登っているとします。階段の頂上に到達するには n 段の階段を登る必要があります。

一度に 1 段または 2 段登ることができます。階段の頂上に到達するための異なる方法は何通りありますか？

例 1：

入力：n = 2
出力：2
説明：階段の頂上に到達するには2つの方法があります。
1. 1段 + 1段
2. 2段

考え方：

1. DP配列とそのインデックスの意味を定義する

ways[i] はi段目に到達するための方法の数を表す

2. 漸化式を決定する

F(n) = F(n - 1) + F(n - 2)

3. DP配列の初期化方法を決定する

この問題ではnは正整数なので、F(0) の値は必要ありません

F(1) = 1、F(2) = 2

配列の長さが3未満の場合、オーバーフローが発生する可能性があるため注意

4. 計算順序を決定する

漸化式 dp[i] = dp[i - 1] + dp[i - 2] から、dp[i] は dp[i - 1] と dp[i - 2] に依存するため、計算順序は前から後ろへとなる

5. DP配列の具体例を導出する

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55........

class Solution {
    public int countWays(int n) {
        if (n <= 2) return n;
        int[] ways = new int[n + 1]; // ways[i]はi段目に到達する方法の数
        ways[1] = 1;
        ways[2] = 2;
        for (int i = 3; i <= n; i++) {
            ways[i] = ways[i - 1] + ways[i - 2]; // i段目に到達するには、i-1段目またはi-2段目からしか来られない
        }
        return ways[n];
    }
}

最小コストでの階段登り

整数配列 cost が与えられます。ここで cost[i] は階段のi番目の段から上へ登るために支払う必要がある費用です。この費用を支払うと、1段または2段上へ登ることができます。

下标为 0 または下标为 1 の段から階段を登り始めることができます。

階段の頂上に到達するための最小費用を計算して返してください。

例 1：

入力：cost = [10, 15, 20]
出力：15
説明：下标为 1 の段から始めます。
- 15を支払い、2段上へ登り、階段の頂上に到達します。
総費用は15です。

例 2：

入力：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
出力：6
説明：下标为 0 の段から始めます。
- 1を支払い、2段上へ登り、下标为 2 の段に到達します。
- 1を支払い、2段上へ登り、下标为 4 の段に到達します。
- 1を支払い、2段上へ登り、下标为 6 の段に到達します。
- 1を支払い、1段上へ登り、下标为 7 の段に到達します。
- 1を支払い、2段上へ登り、下标为 9 の段に到達します。
- 1を支払い、1段上へ登り、階段の頂上に到達します。
総費用は6です。

ヒント：

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

考え方：

1. DP配列とそのインデックスの意味を定義する

dp[i] はi段目に到達するための最小費用を表す

2. 漸化式を決定する

F(n) = min(F(n-1) + cost[i-1], F(n-2) + cost[i-2])

3. DP配列の初期化方法を決定する

下标为 0 または下标为 1 の段から階段を登り始めることができます。

F(0) = 0、F(1) = 0

配列の長さが2未満の場合、オーバーフローが発生する可能性があるため注意

4. 計算順序を決定する

漸化式 F(n) = min(F(n-1) + cost[i], F(n-2) + cost[i-2]) から、dp[i] は dp[i - 1] と dp[i - 2] に依存するため、計算順序は前から後ろへとなる

5. DP配列の具体例を導出する

........

コード：

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        // F(n) = min(F(n-1) + cost[i], F(n-2) + cost[i-2])
        if (cost.length <= 1) {
            return 0;
        }
        int[] minCost = new int[cost.length + 1];
        // minCost[i]: i番目の階段に到達するための最小費用
        // 頂上はcost.length番目の階段
        minCost[0] = 0;
        minCost[1] = 0;
        for (int i = 2; i < minCost.length; i++) {
            minCost[i] = Math.min(minCost[i - 1] + cost[i - 1], minCost[i - 2] + cost[i - 2]);
        }
        return minCost[cost.length];
    }
}

より小さい数

時間制限：1.000S 空間制限：256MB

問題説明

青さんは長さがnで、数字文字0〜9のみからなる文字列を持っています。インデックスは0からn-1までで、これをn桁の10進数numと見なすことができます。青さんはnumから連続する部分文字列を選択し、その部分文字列を反転させることができます。反転は最大1回までです。

青さんは、選択した部分文字列を反転させて元の位置に戻した後の新しい数字numNewが条件numNew < numを満たすようにしたいと考えています。青さんのために、異なる部分文字列の選択方法が何通りあるか計算してください。2つの部分文字列がnum内の位置が完全に同じでない限り、異なる方法と見なします。

注意：先頭に0が存在することを許可します。つまり、数字の最上位桁が0であっても合法です。

入力説明

数字文字0〜9のみからなる長さnの文字列numを含む1行を入力します。左から右へインデックスは0〜n-1です。

出力説明

答えを表す整数を含む1行を出力します。

入力例

210102

出力例

8

ヒント情報

全部で8つの異なる方法があります：

1. 選択した部分文字列のインデックスが0〜1、反転後のnumNew = 120102 < 210102

2. 選択した部分文字列のインデックスが0〜2、反転後のnumNew = 012102 < 210102

3. 選択した部分文字列のインデックスが0〜3、反転後のnumNew = 101202 < 210102

4. 選択した部分文字列のインデックスが0〜4、反転後のnumNew = 010122 < 210102

5. 選択した部分文字列のインデックスが0〜5、反転後のnumNew = 201012 < 210102

6. 選択した部分文字列のインデックスが1〜2、反転後のnumNew = 201102 < 210102

7. 選択した部分文字列のインデックスが1〜4、反転後のnumNew = 201012 < 210102

8. 選択した部分文字列のインデックスが3〜4、反転後のnumNew = 210012 < 210102

データ範囲：
1

もしnum[j] > num[i]なら、反転後、numNew > num

もしnum[j] < num[i]なら、反転後、numNew < num

もしnum[j] == num[i]なら、反転後、i++、j--としてnum[i]とnum[j]の比較を繰り返します。i > jになった場合、部分文字列は回文であり、反転後numNew == numとなります。

動的プログラミングのステップ：

1. DP配列とそのインデックスの意味を定義する

dp[i][j]はnumのiからjまでの部分文字列を反転した後、numNew > numとなるかどうかを表す

2. 漸化式を決定する

if (num[i] > num[j]) dp[i][j] = true;
if (num[i] < num[j]) dp[i][j] = false;
if (num[i] == num[j]) dp[i][j] = dp[i+1][j-1]

3. DP配列の初期化方法を決定する

i < j の場合は不正な部分文字列：dp[i][j] = false

i == j の場合は回文：dp[i][j] = false

4. 計算順序を決定する

漸化式 dp[i][j] = dp[i+1][j-1] から、dp[i][j] は dp[i+1][j-1] に依存するため、計算順序は下から上、左から右へとなる

5. DP配列の具体例を導出する

各自で例を考えてみてください

参考コード：

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String numStr = scanner.next();
        boolean[][] isLarger = new boolean[numStr.length()][numStr.length()];
        // 初期化
        for (int i = 0; i < numStr.length(); i++) {
            for (int j = 0; j <= i; j++) {
                isLarger[i][j] = false;
            }
        }
        int count = 0;
        // 計算
        for (int i = numStr.length() - 2; i >= 0; i--) {
            for (int j = i + 1; j < numStr.length(); j++) {
                if (numStr.charAt(i) == numStr.charAt(j)) {
                    isLarger[i][j] = isLarger[i + 1][j - 1];
                }
                if (numStr.charAt(i) > numStr.charAt(j)) {
                    isLarger[i][j] = true;
                }
                if (numStr.charAt(i) < numStr.charAt(j)) {
                    isLarger[i][j] = false;
                }
                if (isLarger[i][j]) {
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}