Java動的プログラミングの例の分析

説明

1. 動的プログラミングは、非常に複雑な問題をより小さなサブ問題に分割することで解決できるプログラミング原理です。

2. この原理は再帰に似ていますが、再帰とは異なり、それぞれの異なる部分問題は 1 回しか解決できません。

プロセスを使用します

上記の問題に適切な再帰的関係を決定します。

初期メモリ、配列、行列の初期値。

再帰呼び出しを行うとき (サブ質問への回答にアクセスできる)、常に事前に解決されるようにしてください。

例

public class dpSolution {  
    static int getValue(int[] values, int rodLength) {
        int[] subSolutions = new int[rodLength + 1];
 
        for (int i = 1; i <= rodLength; i++) {
            int tmpMax = -1;
            for (int j = 0; j < i; j++)
                tmpMax = Math.max(tmpMax, values[j] + subSolutions[i - j - 1]);
            subSolutions[i] = tmpMax;
        }
        return subSolutions[rodLength];
    }
 
    public static void main(String[] args) {
        int[] values = new int[]{3, 7, 1, 3, 9};
        int rodLength = values.length;
 
        System.out.println("Max rod value: " + getValue(values, rodLength));
    }
}

以上がJava動的プログラミングの例の分析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。