https://www.acmicpc.net/problem/11048
dp
잘못된 접근 : 현재 위치에서, 갈 수 있는 곳만 생각했음
올바른 접근 : 현재 위치를, 올 수 있는 곳을 생각해야함
1 | 1 2 |
d[i][j] : i,j 위치에서의 사탕 개수 최대값
Max(
[i-1][j-1]에서의 사탕개수 최대값,
[i][j-1]에서의 사탕개수 최대값,
[i-1][j]에서의 사탕개수 최대값) + i,j에서의 사탕개수
https://www.acmicpc.net/problem/2167
dp
그림으로 쉽게 풀림
점화식
s[i][j] = a[i][j] + s[i-1][j] +s[i][j-1] - s[i-1][j-1]
( i,j,x,y 의 구간합 )
s[x][y] -s[ i-1][y] - s[x][j-1] + s[i-1][j-1 ]
https://www.acmicpc.net/problem/1149
dp
d[i][color]
i 번째 집을 color 로 칠했을 때, 1 번째~ i 번째 까지 든 최소 비용
d[i+1][0] = i번째 집을 1번으로 칠했을 때 든 최소 비용과, 2번으로 칠했을 때 든 최소비용 중 작은 값
d[i+1][1] = i번째 집을 0번으로 칠했을 때 든 최소 비용과, 2번으로 칠했을 때 든 최소비용 중 작은 값
d[i+1][2] = i번째 집을 0번으로 칠했을 때 든 최소 비용과, 1번으로 칠했을 때 든 최소비용 중 작은 값
https://www.acmicpc.net/problem/10824
