Analyse d'un exemple de programmation dynamique Java

Explication

1. La programmation dynamique est un principe de programmation qui peut être résolu en divisant des problèmes très complexes en sous-problèmes plus petits.

2. Ce principe est similaire à la récursion, mais contrairement à la récursion, chaque sous-problème différent ne peut être résolu qu'une seule fois.

Utilisez le processus

pour déterminer la relation récursive appropriée au problème ci-dessus.

Valeur initiale de la mémoire initiale, du tableau, de la matrice.

Assurez-vous que lorsque nous effectuons un appel récursif (avec accès à la réponse à une sous-question), il est toujours résolu à l'avance.

Instances

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!