프로젝트 오일러 프로젝트 67 - 파이썬

Question

참고 : 나는 나쁜 영어를 가지고, 그것은 나를 판단하지 마십시오 :

문제 :

projecteuler.net/problem=18

오일러 프로젝트 .net/problem = 67

저는 파이썬에서 Project Euler # 67을하고 있습니다.

for i in range(len(temp)): 
    list1 = temp[i] 
    try: 
     list2 = temp[i+1] 
     trynum1 = list1[lastinput] + max(list2[lastinput],list2[lastinput+1]) 
     try: 
      trynum2 = list1[lastinput+1] + max(list2[lastinput+1],list2[lastinput+2]) 
      if trynum1 > trynum2: 
       outputlist.append(list1[lastinput]) 
      else: 
       outputlist.append(list1[lastinput+1]) 
       lastinput += 1 
     except IndexError: 
      outputlist.append(list1[0]) 
    except IndexError: 
     if list1[lastinput] > list1[lastinput+1]: 
      outputlist.append(list1[lastinput]) 
     else: 
      outputlist.append(list1[lastinput+1]) 

변수 :

temp가의 삼각형 프로젝트 18 일 내 프로그램, 프로젝트 67 코드가 작동하지 않습니다는 (파일의 열기 및 정보의 처리를 제외) 정수

outputlist는

내가 대답은 7273 알고 프로그램에 의해 선택된 번호를 저장하는 목록입니다,하지만 내 프로그램은 내가 차 원인이 오류를 찾을 수 없습니다 6542. 발견 전자 상황. O)

논리

이 프로그램에 대한 나의 접근 방식은 하나 개의 번호를 찾을 수 있습니다

(목록 1 : 이미 내 머리가 내 머리를 벗 더니 모두 거의이 프로젝트에 내 머리를 긁적하고 당신은 날 도움이 될 수 있습니다하십시오 [lastinput]) 아래에있는 더 큰 숫자 (trynum1)를 추가하고, 첫 번째 숫자 (list1 [lastinput + 1])의 오른쪽에있는 숫자와 비교하여 그 아래에 2 개의 큰 숫자를 추가하십시오 trynum2). 출력 목록에 큰 것을 추가합니다.

Answer 1

이 접근법은 논리적으로 결함이 있습니다. 1 행에있을 때 오른쪽 또는 왼쪽으로 이동하면 2 행 미리보기가 아니라 최대 합계로 이동하는지 알 수있는 충분한 정보가 없습니다. 최상의 경로를 얻으려면 맨 아래까지 모든 것을 살펴볼 필요가 있습니다.

다른 사람들이 제안했듯이 맨 아래에서 시작하여 해결하십시오. 기억하십시오. 전체 경로는 필요 없으며 합계 만 필요합니다. 각 노드에서 사용 가능한 두 가지 경로 중 더 좋은 노드의 양을 추가합니다. 즉, 해당 노드를 맨 아래로 가져 오는 점수입니다. 상단으로 돌아 가면 temp [0] [0], 그 숫자가 최종 답이어야합니다.