HillHike

Code

public class HillHike

{

    public long numPaths(int distance, int maxHeight, int[] _landmarks) {

        long[][][] cache1 = new long[2][52][51];

        long[][][] cache2 = new long[2][52][51];

        cache1[0][0][0] = 1;

        int[] landmarks = new int[_landmarks.length+1];

        System.arraycopy(_landmarks,0,landmarks,0,_landmarks.length);

        landmarks[_landmarks.length] = -1;

        for (int i = 1; i < distance; i++) {

            cache2 = new long[2][52][51];

            for (int j = 1; j <= maxHeight; j++) {

                int ni = (j == maxHeight) ? 1 : 0;

                for (int k = 0; k < landmarks.length; k++) {

                    int lm = (j == landmarks[k]) ? k + 1 : k;

                    for (int d = -1; d <= 1; d++) {

                        cache2[ni][j][lm] += cache1[0][j+d][k];

                        cache2[1][j][lm] += cache1[1][j+d][k];

                    }

                }

            }

            cache1 = cache2;

        }

        return cache1[1][1][landmarks.length-1];

    }

}

Problem

도보 여행자가 언덕을 등반한다. 특정 거리를 가진 언덕을 높이 0인 시작점에서 올라가 높이 0인 끝점으로 내려와야 한다 (중간에 높이 0인 곳을 방문하지 않아야 한다). 최대 높이를 반드시 거쳐야 하며 최대 높이를 가진 다른 점을 중복해서 방문해도 상관은 없다. 특정 높이에 표지물(landmark)이 존재하며 이를 모두 순서대로 방문해야 한다. 언덕을 내려왔을 때 앞선 조건들을 만족하는 경우의 수를 구하라.

    _____

   / :   : \

  /  :   :  \

 /   :   :   \

/ 1 : 2 : 3 \

종류 1:    오르막길.

종류 2:    평지.

종류 3:    내리막길.

Explanation

동적 프로그래밍을 적용하기 위해서는 먼저 재귀식을 잘 세워야 한다.

f(h,d,lm,max)    h는 현재 높이, d는 현재 거리, lm은 표지물, max는 최대 높이 도달 유무이다.

이 재귀식은 다음의 네 가지 조건을 가진다.

• h = maxHeight, h = landmark[lm]:
  f(h,d,lm,true) = f(h,d-1,lm-1,true) + f(h-1,d-1,lm-1,true) + f(h-1,d-1,lm-1,false)
  f(h,d,lm,false) = 0
• h = maxHeight, h != landmark[lm]:
  f(h,d,lm,true) = f(h,d-1,lm,true) + f(h-1,d-1,lm,true) + f(h-1,d-1,lm,false)
  f(h,d,lm,false) = 0
• h != maxHeight, h = landmark[lm]:
  f(h,d,lm,max) = f(h+1,d-1,lm-1,max) + f(h,d-1,lm-1,max) + f(h-1,d-1,lm-1,max)
  for max = true of false
• h != maxHeight, h != landmark[lm]:
  f(h,d,lm,max) = f(h+1,d-1,lm,max) + f(h,d-1,lm,max) + f(h-1,d-1,lm,max)
  for max = true of false

maxheight = false인 경우와 maxheight = true인 경우를 구분지으면 위 코드가 완성된다.

References

https://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm145