더블릿_계단오르기(dp)

문제정리)

- 시작은 계단으로 치지 않는다.

- 한계단 또는 두계단 씩 오를 수 있다.

- 연속되게 세개의 계단을 밟을 수 없다.

- 계단을 밟을때마다 점수가 오른다.

- 마지막 계단은 반드시 밟아야한다.

- 얻을 수 있는 점수의 최대값을 구하라.

문제풀이)

dp[계단의번호][1] => 지금 계단을 바로 전 계단에서 한 칸 오르는 경우의 최대 값

dp[계단의번호][2] => 지금 계단을 바로 전전 계단에서 두 칸 오르는 경우의 최대 값

초기 계단의 번호 0 과 1은 값을 지정해 준다.

dp[1][1] = arr[1]; dp[1][2] = 0;

dp[2][2] = arr[1] + arr[2]; dp[1][2] = arr[2];

3번 계단부터는 점화식을 통해 dp를 수행한다.

dp[i][1] => 지금 계단을 한 칸으로 오른 경우

dp[i][1] = dp[i-1][2] + arr[i];    => 전 칸까지 2칸으로 오른 경우의 최대 값에 지금 계단의 값을 더함

dp[i][2] => 지금 계단을 두 칸으로 오른 경우

dp[i][2] = max(dp[i-2][1], dp[i-2][2]) + arr[i] => 두 칸 전까지 오른 경우의 최대 값에 지금 계단의 값을 더함