본문 바로가기

카테고리 없음

파이썬 _다이나믹 프로그래밍

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
import sys 
sys.setrecursionlimit(6000000) #재귀 늘리기 위한 부분

arr=[]
def dp(index,A):
    global arr
    
    if index==len(A)-1:				#첫번째 리턴
        return A[-1]

    if arr[index]!=-math.inf:		#가지치기 이미 계산한거 리턴
        return arr[index]
        
    temp=arr[index]

    for i in range( 1,7):			#6가지 경우중 가장 큰값으로 
        if index+i < len(A):
            temp=max(dp(index+i,A)+A[index],temp)
    
    arr[index]=temp
    return arr[index]


import math
def solution(A):
    # write your code in Python 3.6
    global arr
    arr=[-math.inf]*len(A)
    arr[-1]=A[-1]

    return dp(0,A)

https://app.codility.com/demo/results/trainingXXAP3Y-Y8N/