Java - somme Maximale dans le chemin d'accès par le biais d'un tableau 2D

Comme dasblinkenlight dit, le moyen le plus efficace pour ce faire est d'utiliser un memoization ou de la programmation dynamique technique. J'ai tendance à préférer la programmation dynamique, mais je vais l'utiliser pur récursion.

La réponse tourne autour de la réponse à une question fondamentale: "Si je suis dans la place dans la rangée r et de la colonne c sur mon domaine, comment puis-je évaluer le chemin à partir du haut à gauche pour arriver ici, tels que le nombre de fraises est agrandie?"

La clé pour comprendre, c'est qu'il y a seulement deux façons de faire dans la parcelle de terrain dans la ligne r et de la colonne c: je peux y accéder à partir de ci-dessus, à l'aide de la parcelle de terrain dans la ligne r-1 et à la colonne c, ou je peux y arriver par le côté, à l'aide de la parcelle de terrain dans la ligne r et de la colonne c-1. Après cela, vous devez simplement vous assurer de bien connaître votre base de cas...ce qui signifie, fondamentalement, ma purement récursive version serait quelque chose comme:

int[][] field;    
int max(int r, int c) {
    //Base case
    if (r == 0 && c == 0) {
        return field[r][c];
    }
    //Assuming a positive number of strawberries in each plot, otherwise this needs
    //to be negative infinity
    int maxTop = -1, maxLeft = -1;
    //We can't come from the top if we're in the top row
    if (r != 0) {
        maxTop = field[r-1][c];
    }
    //Similarly, we can't come from the left if we're in the left column
    if (c != 0) {
        maxLeft = field[r][c-1];
    }
    //Take whichever gives you more and return..
    return Math.max(maxTop, maxLeft) + field[r][c];
}

Appel max(r-1, c-1) pour obtenir une réponse. Notez qu'il y a beaucoup d'inefficacité ici; vous allez faire beaucoup mieux en utilisant la programmation dynamique (que je vais donner ci-dessous) ou memoization (qui a déjà été défini). La chose à retenir, cependant, est que le DP et memoization techniques sont simplement des moyens plus efficaces qui viennent de l'récursive principes utilisés ici.

DP:

int maxValue(int[][] field) {
    int r = field.length;
    int c = field[0].length;
    int[][] maxValues = new int[r][c];
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (i == 0 && j == 0) {
                maxValues[i][j] = field[i][j];
            } else if (i == 0) {
                maxValues[i][j] = maxValues[i][j-1] + field[i][j];
            } else if (j == 0) {
                maxValues[i][j] = maxValues[i-1][j] + field[i][j];
            } else {
                maxValues[i][j] = Math.max(maxValues[i][j-1], maxValues[i-1][j]) + field[i][j];
            }
        }
    }
    return maxValues[r-1][c-1];
}

Dans les deux cas, si vous souhaitez recréer le chemin réel, il suffit de garder un 2D tableau de booléens correspondant à "N'ai-je venir d'en haut ou à gauche"? Si la plupart des fraises chemin vient d'en haut, mettez vrai, autrement dit de faux. Qui peut vous permettre de retracer le patch après le calcul.

Avis que c'est tout de même récursive en principe: à chaque étape, nous sommes à la recherche de retour à nos résultats précédents. Nous venons d'arriver à être mise en cache de nos résultats précédents, afin de ne pas gaspiller un tas de travail, et nous attaquons la sous-problèmes dans un système intelligent de commande afin que nous puissions toujours les résoudre. Pour en savoir plus sur la programmation dynamique, voir Wikipédia.

OriginalL'auteur DivineWolfwood

Vous pouvez résoudre ce problème avec DP tabulation méthode, avec lequel vous pouvez économiser de l'espace de O(m*n) à O(n). Avec DP Mémorisation, vous devez m*n de la matrice de stocker des valeurs intermédiaires. Voici mon code Python. J'espère que ça peut aider.

def max_path(field):
    dp = [sum(field[0][:i]) for i in range(1, len(field[0]) + 1)]
    for i in range(1, len(field)):
        for j in range(len(dp)):
            dp[j] = min(dp[j], dp[j - 1] if j > 0 else float('inf')) + field[i][j]
    return dp[-1]

OriginalL'auteur Jonathon.lau