정수 배열의 경로 수

Question

예를 들어 정수 배열이 있습니다.

{3,1,2,7,5,6}

한 번에 배열 앞으로 각 요소 중 하나를 이동하거나 그 인덱스 값에 기초하여 몇 가지 요소를 이동할 수있다. 예를 들어, 하나는 3에서 1 또는 3에서 7로 갈 수 있고, 그 다음 하나는 1에서 2 또는 1에서 2로 갈 수 있고 (여기서 점프 할 수 없음), 그러면 하나는 2에서 7 또는 2에서 5로 갈 수 있고, 하나는 갈 수 있습니다 7에서 5의 coz 지수 만이 3이고 7에서 3 = 10을 추가하고 열 번째 요소가 없습니다.

시작 인덱스에서 배열 끝까지 도달 할 수있는 경로 수만 계산해야합니다.

난 단지 재귀 적으로 그리고 순진한 기하 급수적으로 실행됩니다.

누군가 plz 도움.

Answer 1

내 권장 사항 : 동적 프로그래밍을 사용하십시오.

이 키워드로 충분하고 도전 과제를 원하는 해결 방법을 찾으려면 더 이상 읽지 마십시오!

예를 들어 입력 {3,1,2,7,5,6}에 가능한 DP 알고리즘이 있습니다. 일반적인 문제에 적응하는 것이 당신의 일이 될 것입니다.

길이가 6 인 배열 sol을 만듭니다. 배열은 많은 수의 길을 유지합니다.

sol[5] = 1; 
for (i = 4; i>=0;i--) { 
    sol[i] = sol[i+1]; 
    if (i+input[i] < 6 && input[i] != 1) 
     sol[i] += sol[i+input[i]];    
} 

return sol[0]; 

런타임 O (N) 주석을 암시 방향성 그래프 용액로서는

는 :

배열의 각 셀은 노드를 나타낸다. 각 노드에서 노드에 대한 접근 가능한 방향을 지정하십시오. 기본적으로 노드의 이상을 살펴봄으로써 방향의 수를 계산할 수 있습니다 (지시 사이클이 없으므로). 그러나 실제 프로그램을 작성하는 보일러 플레이트가 많습니다.

재귀 솔루션

또 다른 솔루션을 조정 치기하는 것입니다. 이것은 기본적으로 DP 알고리즘과 동일합니다. exponentiel 시간은 값을 여러 번 계산한다는 사실에서 비롯됩니다. 예 : 기능은 recfunc(index)입니다. 초기 전화 recFunc(0)은 recFunc(1) and recFunc(3) 등으로 전화합니다. 그러나 recFunc(3)은 다시 어딘가에 호출되도록 바인딩되어 반복적 인 계산을 반복합니다. 이것을 제거하려면 Map을 추가하여 이미 계산 된 값을 모두 보유하십시오. recFunc(x)로 전화를 걸면 x이 이미 계산 된 경우지도에서 검색합니다. 예인 경우 저장된 값을 반환하십시오. 그렇지 않다면 계산하여 저장하고 반환하십시오. 이렇게하면 O (n)도 얻을 수 있습니다.