이동하기

https://www.acmicpc.net/problem/11048

풀이

• dp

• 잘못된 접근 : 현재 위치에서, 갈 수 있는 곳만 생각했음

• 올바른 접근 : 현재 위치를, 올 수 있는 곳을 생각해야함

  1 2
  3 4
  
  4를 올 수 있는 곳은 1, 2, 3

• d[i][j] : i,j 위치에서의 사탕 개수 최대값

  Max(
  ​ [i-1][j-1]에서의 사탕개수 최대값,
  ​ [i][j-1]에서의 사탕개수 최대값,
  ​ [i-1][j]에서의 사탕개수 최대값) + i,j에서의 사탕개수