java動態規劃實例分析

說明

1、動態規劃是一種程式設計原理，可以透過將非常複雜的問題分成較小的子問題來解決。

2、這個原則類似遞歸，但不同於遞歸，每個不同的子問題只能解決一次。

使用流程

確定適合上述問題的遞迴關係。

初始記憶體，陣列，矩陣的初始值。

確保當我們進行遞歸呼叫(可以存取子問題的答案)時，總是事先解決。

實例

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中文網其他相關文章！