오일러 # 18 with

Question

project euler problem 18을 해결하려고합니다. http://projecteuler.net/problem=18 파이썬이 삼각형 바닥에서 작동하는 그리 디 알고리즘을 시도했습니다. THEN 나는 한 행 위로 올라가고 탐욕스러운 알고리즘으로 가장 큰 경로를 찾고 가장 큰 경로를 연결하려고 시도하지만 작동하지 않습니다. 문제 해결 방법을 제시하지 않고 올바른 방향으로 나아갈 수있는 힌트가 있습니까?

def greedy(i): 
    if i%15==0: 
     a=[(b[i-15],i-15),(b[i-14],i-14)] 
     a=sorted(a) 
     a=a[-1] 
    else: 
     a=[(b[i-15],i-15),(b[i-16],i-16),(b[i-14],i-14)] 
     a=sorted(a) 
     a=a[-1] 
    return a 

건배

Answer 1

혹시 Dynamic Programming 들어 본 적이 : 여기

는 기능입니다?

이 문제를 고려하십시오. 경로가 가장 좋은 점은 무엇입니까? 마지막 단계와 이전 단계 사이에 어떤 관계가 있습니까? 또한 탐욕적인 알고리즘이 올바른 답을주지 못하는 삼각형을보십시오 :

 1 
    2 3 
    9 1 2 
1 1 2 4