[GO] Zu beachtende Punkte bei der Lösung von DP-Problemen mit Python

Überblick

Als ich das DP-Problem (Dynamic Programming) von AtCoder löste, stieß ich auf das Phänomen, dass der Code, der in anderen Sprachen AC wäre, TLE wäre, wenn es Python / PyPy wäre, also werde ich ihn als Memorandum belassen.

Über DP-Problem

Wie in diesem Artikel ausführlich erläutert, gibt es verschiedene Möglichkeiten, das DP-Problem zu lösen. Grob gesagt wird die for-Anweisung von unten nach oben gedreht. Es gibt zwei Methoden: Die eine besteht darin, eine DP-Tabelle zu erstellen, und die andere darin, dass eine Wiederholung von Erinnerungen rekursive Funktionen von oben nach unten aufruft. In jedem Fall ist es insofern dasselbe, als es die Verarbeitung beschleunigt, indem das berechnete Ergebnis beibehalten wird. Im Falle einer Wiederholung von Gedenkstätten entsteht jedoch ein Overhead des Funktionsaufrufs, sodass es in einigen Sprachen innerhalb des Zeitlimits liegt. Es kann vorkommen, dass der Vorgang nicht abgeschlossen ist und TLE wird.

Beispiel

DP-Zusammenfassungswettbewerb B Problem: Frosch2

Lösung 1: Bottom-up DP von für Anweisung

N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [10**9] * N

for i in range(N):
    if i == 0:
        dp[0] = 0
    elif i == 1:
        dp[1] = abs(h[0]-h[1])
    else:
        for j in range(1, K+1):
            if j > i:
                break
            dp[i] = min(dp[i], dp[i - j] + abs(h[i - j] - h[i]))

print(dp[N-1])

Ergebnis

In Python einreichen ist TLE und In PyPy einreichen ist AC ). Sie können AC auch erhalten, indem Sie ähnlichen Code in einer schnellen Sprache wie Go schreiben.

Lösung 2: Wiederholung der Speicherung (Anzahl der Funktionsaufrufe: groß)

Wenn in Python geschrieben

import sys
sys.setrecursionlimit(10**6)

N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = 10**9
dp = [INF] * N

def solve(n):
    if dp[n] != INF:
        return dp[n]

    if n == 0:
        dp[n] = 0
    elif n == 1:
        dp[n] = abs(h[0] - h[1])
    else:
        for i in range(1, K + 1):
            if n - i < 0:
                break
            cost = solve(n - i) + abs(h[n - i] - h[n])
            dp[n] = min(dp[n], cost)

    return dp[n]

print(solve(N-1))

Wenn in Go geschrieben

package main

import (
	"fmt"
	"math"
)

var (
	N, K, INF int
	h, dp []int
)

func solve(n int) int {
	if dp[n] != INF {
		return dp[n]
	}

	if n == 0 {
		dp[n] = 0
	} else if n == 1 {
		dp[n] = int(math.Abs(float64(h[n] - h[n-1])))
	} else {
		for i := 1; i <= K; i++ {
			if n - i < 0 {
				break
			}
			var cost =  solve(n - i) + int(math.Abs(float64(h[n-i]-h[n])))
			dp[n] = int(math.Min(float64(dp[n]), float64(cost)))
		}
	}

	return dp[n]
}

func main() {
	fmt.Scan(&N, &K)
	h = make([]int, N)
	dp = make([]int, N)
	INF = int(math.Pow(10, 9))

	for i := 0; i < N; i++ {
		fmt.Scan(&h[i])
	}
	for i := 0; i < N; i++ {
		dp[i] = INF
	}

	fmt.Println(solve(N - 1))
}

Ergebnis

Es handelt sich um eine sogenannte gewöhnliche rekursive Memokonvertierung, die jedoch zu TLE bei Übermittlung mit Python oder PyPy und Schreiben und Übermitteln in einer Hochgeschwindigkeitssprache wie Go Dann wird es AC. Um AC mit Python / PyPy zu betreiben, ist ein anderes Gerät erforderlich.

Lösung 3: Wiederholung der Speicherung (Anzahl der Funktionsaufrufe: klein)

import sys
sys.setrecursionlimit(10**6)

N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = 10**9
dp = [INF] * N

def solve(n):
    if dp[n] != INF:
        return dp[n]

    if n == 0:
        dp[n] = 0
    elif n == 1:
        dp[n] = abs(h[0] - h[1])
    else:
        for i in range(1, K+1):
            if n - i < 0:
                break
            if dp[n - i] != INF:
                #Dp, um die Anzahl der Funktionsaufrufe zu reduzieren[n-i]Verwenden Sie es, wenn es bereits berechnet wurde
                cost = dp[n - i] + abs(h[n - i] - h[n])
            else:
                cost = solve(n - i) + abs(h[n - i] - h[n])
            dp[n] = min(dp[n], cost)

    return dp[n]

print(solve(N-1))

Ergebnis

Der Code ist fast der gleiche wie in Lösung 2, prüft jedoch in diesem Fall, ob dp [n-i] berechnet wurde, bevor Sie lösen (n-i) aufrufen. Wenn er berechnet wird, wird er verwendet. Auf diese Weise können Sie den Overhead des Funktionsaufrufs reduzieren und ihn [AC mit PyPy] erstellen (https://atcoder.jp/contests/dp/submissions/14453556). Trotz dieses Einfallsreichtums wird es jedoch [TLE bei Übermittlung in Python] sein (https://atcoder.jp/contests/dp/submissions/14453565).

Zusammenfassung

Die Ergebnisse für jede Lösung und Sprache sind wie folgt. Mit anderen Worten, wenn Sie es in Python einreichen, können Sie AC verwenden, ohne sich besonders der Hochgeschwindigkeitssprachen wie AC und Go bewusst zu sein, wenn Sie TLE und PyPy entwickeln.

Daher ist es möglicherweise eine gute Idee, das DP-Problem in einer Hochgeschwindigkeitssprache wie C ++ oder Go einzureichen. Wenn Sie es wirklich mit Python lösen möchten, sollten Sie Folgendes beachten.

• Wenn möglich, führen Sie eine Bottom-up-DP mit einer for-Anweisung anstelle einer Wiederholung des Memorandums durch.
• Reduzieren Sie bei der Wiederholung von Gedenkstätten die Anzahl der Funktionsaufrufe so weit wie möglich (überprüfen Sie die DP-Tabelle, bevor Sie die Funktion aufrufen). --Senden Sie in PyPy anstelle von Python

Wenn Sie andere Fehler haben, wie z. B. Punkte, die Sie bemerkt haben oder die Sie erkannt haben, wäre es hilfreich, wenn Sie darauf hinweisen könnten.