Java 프로그래밍 : 계단에서의 동적 프로그래밍 예 :

Question

남자가 n 개의 계단으로 계단을 오르고 있으며 한 번에 1 단계, 2 단계 또는 3 단계로 갈 수 있습니다. 이제 자녀가 계단을 달릴 수있는 방법을 세는 프로그램을 작성하십시오. 주어진

코드는 내가 JAVA, C 및 C++을 알지

public static int countDP(int n, int[] map) { 
if (n<0) 
    return 0; 
else if (n==0) 
    return 1; 
else if (map[n]>-1) 
    return map[n]; 
else { 
    map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map); 
    return map[n]; } 
} 

이하 같다. 이것은 Cracking the Coding 인터뷰 책에서 발췌 한 것입니다. 은 아무도

1. 이유를 설명 할 수 없습니다 어떻게 그녀는 여기에 기능 맵을 사용? 여기의지도는 바로 배열입니까?

2. 지도 배열에 입력을 저장하는 행이 표시되지 않지만 어떻게 반환합니까?

3. 누구나이 코드의 C++ 또는 C 버전 아이디어가 있습니까? 이 코드를 이해하기 어렵습니다. 어쩌면 자바 문법 때문에가 아니라 동적 프로그래밍의 암시 적 구조 때문일 수 있습니다.

4. 이 알고리즘의 시간 복잡도는 어떻게됩니까? 그것은 O (3^n)보다 작아야합니까?

나는 크게 감사하겠습니다.

감사합니다, 여러분

Answer 1

자, 코드가하는 것이 있습니다.

`if (n<0)` 
    `return 0;` 

충분한 단계가 남아 있지 않으면 계산하지 마십시오. 예를 들어 두 단계가 남아 있지만 사용자가 세 단계를 수행하려는 경우 가능한 조합으로 간주되지 않습니다.

else if (n==0) 나머지 단계의 수는 사용자가 수행하려고 가능한 단계의 수와 일치하는 경우 return 1;

, 그것은 가능한 조합이다. 따라서 가능한 조합이므로 유효한 조합의 총 개수에 1을 더해야하므로 1을 반환합니다.

else if (map[n]>-1) return map[n];

여기서 동적 프로그래밍의 일부이다. 배열의 모든 값의 값이 -1이라고 가정합니다. 따라서 숫자가 -1보다 큰 경우 이미 해결되었으므로 해결하지 않고 단계 번호 n에서 총 조합 수를 반환합니다.

return map[n]; }

`map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map);` 

마지막으로,이 제품은 코드를 해결한다. 가능한 조합의 수는 사용자가 얻을 수있는 가능한 조합의 수와 같습니다. 1 단계 걸리는 경우 + 사용자가 얻을 수있는 조합의 수 (2 단계 소요 + 사용자가 얻을 수있는 가능한 조합의 수) 3 단계.

//The number of solutions from the fifth step 

countDp(5) = countDp(4)+countDp(3)+countDp(2); 

//Number of solutions from the fourth step 

countDP(4) = countDp(3)+countDp(2)+countDp(1); 

//Number of solutions from the third step 

countDp(3) = countDp(2)+countDp(1)+countDp(0); 
//Number of solutions from the second step 
countDp(2) = countDp(1)+countDp(0)+countDp(-1); 
//Number of solutions from the first step 
countDp(1) = countDp(0) + countDp(-1)+countDp(-2); 
//Finally, base case 
countDp(0) = 1; 

countDp(-1)= 0; 
countDp(-2)= 0; 
countDp(1) = 1+0+0 = 1; 
countDp(2) = 1+1+0 = 2; //Dynamic programming: did not have to resolve for countDp(1), instead looked up the value in map[1] 
countDp(3) = 2+1+1 = 4; //Dynamic programming, did not have to solve for countDp(1), countDp(2), instead looked up value in map[1] and map[2] 
countDp(4) = 4+2+1=7 //Dynamic programming, did not have to solve for CountDp(3),CountDp(2), CountDp(1), just looked them up in map[3],map[2],map[1] 
countDp(5)= 2+4+7=13 //Dynamic programming, just used map[4]+map[3]+map[2] 

Answer 2

왜 그녀가 여기에 기능 맵을 사용하는 방법?

이 책에는 memoization이라는 동적 프로그래밍 기법이 나와 있습니다. 동일한 수를 다시 계산하는 것을 피하기 위해 사용됩니다. 요소가 -1이 아닌 경우 다시 계산되고 다시 계산하면 CPU 사이클이 많이 낭비됩니다. DP는 값을 한 번 계산 한 다음 값이 필요할 때마다 값을 반환합니다.

지도는 여기에 있습니다.

정확함, map은 배열 유형입니다.

입력을지도 배열에 저장하는 데 어떤 행도 표시되지 않지만 어떻게 반환합니까?

바닥에서 세 번째 줄에 할당 될 것이다

:

map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map); 

누구는 C++ 또는이 코드의 C 버전의 아이디어가있다? 이 코드를 이해하기 어렵습니다. 어쩌면 자바 문법 때문에가 아니라 동적 프로그래밍의 암시 적 구조 때문일 수 있습니다.

오른쪽, DP 및 memoization에 익숙해 지려면 약간의 시간이 필요합니다. 적은 수의 말로 종이와 연필로이 알고리즘을 한 번 실행합니다. 예를 들어 10이라고하면 답의 최적 하부 구조가 어떻게이 알고리즘이 그 답을 빨리 찾아 낼 수 있는지를 알 수 있습니다.

이 알고리즘의 시간 복잡도는 어떻게됩니까? 그것은 O (3^n)보다 작아야합니까?

물론입니다! 각 항목은 정확히 한 번 계산되며 각 항목은 상각 된 O(1)을 사용하여 계산하므로이 코드의 전체적인 복잡도는 O(N)입니다. 이는 반 직관적 일 수 있습니다. countDP(K)을 계산하는 순환 호출 체인이 O(K) 회귀 호출을받는 방식을 관찰 할 때 그렇습니다. 그러나 각 호출은 map의 K 항목의 계산을 완료합니다 (단, map은 단방향 길임에 유의하십시오. 일단 음수가 아닌 값을 셀에 설정하면 영원히 부정적이지 않게되므로 다시 계산합니다. 다른 호출 경로를 통한 같은 값은 동일한 O(1) 시간을 취합니다.

Answer 3

1) map은 정수 배열입니다. Java의 표기법은 map [n]이 인덱스 n에서 정수 값을 리턴한다는 것입니다.

2. map [n]이 인덱스 n에서 정수 값을 반환하기 때문에 반환 값은 정수입니다. 값은 어레이에 저장되는 유일한 시간이 모든 가능한 1, 2, 3의 조합을 계산하여 단계의 합계를 찾는 재귀 호출이

map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map); 

이다.

3)

int countDP(int n, int map[]) 
{ 
if (n<0) 
    return 0; 
else if (n==0) 
    return 1; 
else if (map[n]>-1) 
    return map[n]; 
else { 
    map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map); 
    return map[n]; 
} 


} 

4) 예 복잡도는 O^N (3)보다 훨씬 빠른 것이다.

Answer 4

자바 스크립트 솔루션 : (반복)

function countPossibleWaysIterative(n) { 
    if (n < 0){ 
    return -1; // check for negative, also might want to check if n is an integer 
    } if (n === 0) { 
    return 0; // for case with 0 stairs 
    } else if (n === 1) { 
    return 1; // for case with 1 stairs 
    } else if (n === 2) { 
    return 2; // for case with 2 stairs 
    } else { 

    var prev_prev = 1; 
    var prev = 2; 
    var res = 4; // for case with 3 stairs 

    while (n > 3) { // all other cases 
     var tmp = prev_prev + prev + res; 
     prev_prev = prev; 
     prev = res; 
     res = tmp; 
     n--; 
    } 
    } 
    return res; 
} 

Answer 5

/** 
* Created by mona on 3/3/16. 
*/ 
import java.util.Hashtable; 
public class StairCount { 
    /* 
    A man is running up a staircase with n steps, and can go either 1 steps, 2 steps, 
     or 3 steps at a time. count how many possible ways the child can run the stairs. 
    */ 
    static Hashtable<Integer, Long> ht=new Hashtable<>(); 

    public static long stairs(int n){ 
     if (!ht.containsKey(1)){ 
      ht.put(1, (long) 1); 
     } 
     if (!ht.containsKey(2)){ 
      ht.put(2, (long) 2); 
     } 
     if (!ht.containsKey(3)){ 
      ht.put(3, (long) 4); 
     } 

/* 
     if (!ht.containsKey(n)){ 
      ht.put(n, stairs(n-1)+ht.get(1)+stairs(n-2)+ht.get(2)+stairs(n-3)+ht.get(3)); 
     } 
*/ 
     if (!ht.containsKey(n)){ 
      ht.put(n, stairs(n-1)+stairs(n-2)+stairs(n-3)); 
     } 
     return ht.get(n); 
    } 
    public static void main(String[] args){ 
     System.out.println(stairs(4)); 

    } 
} 

// 대답

예, 5 간단한 실행의 모습

단계가있는 가정 4는 14이고 5는 27입니다. 주석 처리 된 행의 경우. 누군가 내 생각 과정이 잘못된 이유를 설명 할 수 있습니까?