✅ DP
문제
링크
1. 문제 접근 및 해결 로직
이전 위치에 따라 사탕 개수가 달라진다.
사탕 개수는 최대가 되야 하므로
1. 왼쪽 위에서 온 경우
2. 위에서 온 경우
3. 왼쪽에서 온 경우
중에 사탕 개수가 최대가 되는 값을 넣어주면 된다.
- 정의
dp[i][j] : (i,j)에서 사탕의 최대 개수
- 구하는 답
dp[N][M]
- 초기값
dp[1][1]=candy[1][1]
- 점화식
dp[i][j]=max(dp[i−1][j−1],max(dp[i−1][j],dp[i][j−1]))+candy[i][j]
2. 코드
3. 시간 복잡도 분석
경우의 수를 모두 구하므로
O(N)
4. 문제에서 중요한 부분
DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항
