Was ist der Unterschied zwischen Memoisierung und dynamischer Programmierung?

Question

Was ist der Unterschied zwischen Memoisierung und dynamischer Programmierung? Ich denke, dass die dynamische Programmierung eine Untermenge der Memoisierung ist. Ist das richtig?

Answer 1

Aus wikipedia:

Memoisierung

In der Datenverarbeitung ist die Memoisierung eine Optimierungstechnik um Computerprogramme zu beschleunigen, indem Funktionsaufrufe die Wiederholung von die Berechnung von Ergebnissen für zuvor verarbeitete Eingaben vermeiden.

Dynamische Programmierung

In der Mathematik und Informatik ist die dynamische Programmierung eine Methode zur Lösung komplexer Probleme durch deren Zerlegung in einfachere Teilprobleme.

Wenn wir ein Problem in kleinere/einfachere Teilprobleme zerlegen, stoßen wir oft mehr als einmal auf dasselbe Teilproblem - daher verwenden wir Memoization, um die Ergebnisse früherer Berechnungen zu speichern, damit wir sie nicht wiederholen müssen.

Bei der dynamischen Programmierung gibt es oft Situationen, in denen es sinnvoll ist, die Memoisierung zu verwenden, aber Sie können beide Techniken verwenden, ohne unbedingt die andere zu benutzen.

Answer 2

Ich würde gerne mit einer Beispiel ;

Problem:

Sie steigen eine Treppe hinauf. Sie brauchen n Stufen, um nach oben zu gelangen.

Jedes Mal können Sie entweder 1 oder 2 Stufen steigen. Auf wie viele verschiedene Arten kannst du nach oben klettern?

Rekursion mit Memoisierung

Auf diese Weise beschneiden wir den Rekursionsbaum mit Hilfe des Memo-Arrays und reduzieren die Größe des Rekursionsbaums bis zu nn.

public class Solution {
    public int climbStairs(int n) {
        int memo[] = new int[n + 1];
        return climb_Stairs(0, n, memo);
    }
    public int climb_Stairs(int i, int n, int memo[]) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        if (memo[i] > 0) {
            return memo[i];
        }
        memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
        return memo[i];
    }
}

Dynamische Programmierung

Da wir sehen, dass dieses Problem in Teilprobleme zerlegt werden kann und die Eigenschaft der optimalen Substruktur besitzt, d.h. seine optimale Lösung kann effizient aus den optimalen Lösungen seiner Teilprobleme konstruiert werden, können wir zur Lösung dieses Problems dynamische Programmierung verwenden.

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

Beispiele aus https://leetcode.com/problems/climbing-stairs/

Answer 3

Denken Sie nur an zwei Möglichkeiten,

1. Wir zerlegen das größere Problem in kleinere Teilprobleme - Top-down-Ansatz.
2. Wir gehen vom kleinsten Teilproblem aus und erreichen das größere Problem - Bottom-up-Ansatz.

En Memoisierung verwenden wir (1.), wo wir jeden Funktionsaufruf in einem Cache speichern und von dort aus zurückrufen. Das ist ein bisschen teuer, da es rekursive Aufrufe beinhaltet.

En Dynamische Programmierung gehen wir mit (2.) vor, wo wir eine Tabelle pflegen, von unten nach oben, indem wir Teilprobleme unter Verwendung der in der Tabelle gespeicherten Daten lösen, allgemein als dp-Tabelle bezeichnet.

Anmerkung:

• Beide sind auf Probleme mit überlappenden Teilproblemen anwendbar.

• Die Memoisierung schneidet aufgrund des Overheads, der bei rekursiven Funktionsaufrufen entsteht, vergleichsweise schlechter ab als DP.

• Die asymptotische Zeitkomplexität bleibt dieselbe.

Answer 4

Es gibt einige Ähnlichkeiten zwischen dynamische Programmierung (DP) und Memoisierung und in den meisten Fällen können Sie einen dynamischen Programmierprozess durch Memoisierung implementieren und umgekehrt. Es gibt jedoch einige Unterschiede, die Sie bei der Entscheidung für einen Ansatz berücksichtigen sollten:

• Memoisierung ist ein Top-Down-Ansatz bei dem man ein großes Problem in kleinere Teilprobleme mit den gleichen Eigenschaften zerlegt, und wenn die Größe klein genug ist, kann man es leicht durch Brute-Forcing lösen. Dynamische Programmierung ist ein Bottom-up-Ansatz bei dem Sie zunächst die Antwort auf kleine Fälle berechnen und diese dann zur Konstruktion der Antwort auf große Fälle verwenden.
• Während der Codierung wird die Memoisierung in der Regel implementiert durch Rekursion während die dynamische Programmierung die Berechnung durch Iteration . Wenn Sie also die Raum- und Zeitkomplexität Ihres Algorithmus sorgfältig berechnet haben, kann Ihnen die Implementierung im Stil der dynamischen Programmierung eine bessere Leistung bieten.
• Es gibt Situationen, in denen die Verwendung der Memoisierung Vorteile hat. Die dynamische Programmierung muss berechnen jede Teilproblem, weil es nicht weiß, welches davon in Zukunft nützlich sein wird. Aber die Memoisierung berechnet nur die Teilprobleme im Zusammenhang mit dem ursprünglichen Problem . Manchmal kann man einen DV-Algorithmus mit einer theoretisch enormen Menge an DV-Status entwerfen. Durch sorgfältige Analysen stellt man jedoch fest, dass nur eine akzeptable Menge davon verwendet wird. In dieser Situation ist es vorzuziehen, Memoisierung zu verwenden, um enorme Ausführungszeiten zu vermeiden.

Answer 5

En Dynamische Programmierung ,

• Kein Overhead für Rekursion, weniger Overhead für die Pflege der Tabelle.
• Das regelmäßige Muster der Tabellenzugriffe kann genutzt werden, um den Zeit- oder Platzbedarf zu reduzieren.

En Auswendiglernen ,

• Einige Teilprobleme müssen nicht gelöst werden.