Analisis contoh pengaturcaraan dinamik Java

Penjelasan

1. Pengaturcaraan dinamik ialah prinsip pengaturcaraan yang boleh diselesaikan dengan membahagikan masalah yang sangat kompleks kepada sub-masalah yang lebih kecil.

2. Prinsip ini serupa dengan rekursi, tetapi tidak seperti rekursi, setiap sub-masalah yang berbeza hanya boleh diselesaikan sekali.

Gunakan proses

untuk mengenal pasti hubungan berulang yang sesuai untuk masalah di atas.

Nilai awal memori awal, tatasusunan, matriks.

Pastikan apabila kami membuat panggilan rekursif (dengan akses kepada jawapan kepada sub-soalan), ia sentiasa diselesaikan lebih awal daripada masa.

Instance

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));
    }
}

Atas ialah kandungan terperinci Analisis contoh pengaturcaraan dinamik Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!