[GO] Points à noter lors de la résolution de problèmes DP avec Python

Aperçu

Lorsque je résolvais le problème DP (programmation dynamique) d'AtCoder, j'ai rencontré un phénomène selon lequel le code qui serait AC dans d'autres langages serait TLE s'il s'agissait de Python / PyPy, je le laisserai donc comme un mémorandum.

À propos du problème DP

Comme expliqué en détail dans cet article, il existe plusieurs façons de résoudre le problème DP, mais si vous le divisez grossièrement, activez l'instruction for de bas en haut. Il existe deux méthodes, l'une consiste à créer une table DP et l'autre est la récurrence mémorielle qui appelle des fonctions récursives de haut en bas. Dans tous les cas, il en est de même en ce sens qu'il accélère le traitement en conservant le résultat calculé, mais dans le cas de récurrence mémorielle, il y a un surcoût d'appel de fonction, donc c'est dans le délai dans certaines langues. Il y a des moments où le processus ne se termine pas et devient TLE.

exemple

Problème du concours récapitulatif DP B: Frog2

Solution 1: DP de bas en haut par instruction for

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])

résultat

Soumettre en Python sera TLE et Soumettre en PyPy sera AC ). Vous pouvez également obtenir AC en écrivant un code similaire dans un langage rapide tel que Go.

Solution 2: récurrence de la mémorisation (nombre d'appels de fonction: grand)

Lorsqu'il est écrit en Python

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

Lorsqu'il est écrit en Go

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

résultat

Il s'agit d'une conversion récursive dite de mémo ordinaire, mais elle devient TLE lorsqu'elle est soumise avec Python ou PyPy, et [Écrire et soumettre dans un langage à grande vitesse tel que Go] Ensuite, il devient AC](https://atcoder.jp/contests/dp/submissions/14452835). Afin de prendre AC avec Python / PyPy, un autre appareil est nécessaire.

Solution 3: récurrence de la mémorisation (nombre d'appels de fonction: petit)

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 pour réduire le nombre d'appels de fonction[n-i]Utilisez-le s'il est déjà calculé
                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))

résultat

C'est presque le même code que la solution 2, mais dans ce cas, il vérifie si dp [n-i] a été calculé avant d'appeler résoudre (n-i), et s'il est calculé, il est utilisé. En faisant cela, vous pouvez réduire la surcharge de l'appel de fonction et le rendre AC avec PyPy. Cependant, même avec cette ingéniosité, ce sera TLE une fois soumis en Python.

Résumé

Les résultats pour chaque solution et langue sont les suivants. En d'autres termes, si vous le soumettez en Python, vous pouvez prendre AC sans être particulièrement conscient des langages à haute vitesse tels que AC et Go si vous concevez TLE et PyPy.

Par conséquent, il peut être judicieux de soumettre le problème DP dans un langage à grande vitesse tel que C ++ ou Go. Si vous voulez vraiment le résoudre avec Python, vous devez être conscient de ce qui suit.

• Si possible, effectuez un DP ascendant avec une déclaration for au lieu de la récurrence du mémorandum.
• Lors de l'exécution d'une récurrence commémorative, réduisez le nombre d'appels de fonction autant que possible (vérifiez la table DP avant d'appeler la fonction) --Soumettre en PyPy au lieu de Python

Si vous avez d'autres erreurs telles que des points que vous avez remarqués ou une reconnaissance, il serait utile que vous puissiez les signaler.