두 문제 모두 같은 유형의 동적 계획법 문제이다. 동적 계획법을 사용하기 위한 조건은
겹치는 부분 문제 (Overlapping Subproblems)
최적 부분 구조(Optimal SubStructure)
이다.
정수 삼각형 문제에서는 dp[i][j]를 i,j 위치에서의 최댓값이라고 정의하면, dp[i-1][j], dp[i-1][j-1] 값이 재사용 된다. 그리고 각 부분 문제들 전체 문제의 최적해가 되기 때문에 최적 부분 구조 조건 또한 만족하게 된다.
등굣길 문제 또한 dp[i][j]를 i,j 위치까지 최단거리의 수라고 정의하면, dp[i-1][j],dp[i][j-1] 값이 재사용 된다. 마찬가지로 최적 부분 구조 조건 또한 만족한다.
두 문제는 동적계획법 문제를 조금 풀어봤다면 대표적인 예제들이기 때문에 쉽게 풀었을 것 같다. 조금 짜증 나는건 등굣길에서는 x,y 좌표 값이 행,열이 아니라 열,행 으로 주어진 다는 점? 이 부분만 주의하면 된다.
정수 삼각형
def solution(triangle):
n = len(triangle)
dp = [[0] * n for _ in range(n)]
dp[0][0] = triangle[0][0]
for i in range(1,len(triangle)):
for j in range(i+1):
left = j -1
right = j
if left >= 0:
dp[i][j] = max(dp[i][j], dp[i-1][left] + triangle[i][j])
if right < i:
dp[i][j] = max(dp[i][j], dp[i-1][right] + triangle[i][j])
return max(dp[-1])등굣길
def solution(m, n, puddles):
answer = 0
maps = [[True] * m for _ in range(n)]
dp = [[0] * m for _ in range(n)]
for puddle in puddles:
x = puddle[0]-1
y = puddle[1]-1
maps[y][x] = False
dp[0][0] = 1
for i in range(1,m):
if maps[0][i] and dp[0][i-1]:
dp[0][i] = 1
for i in range(1,n):
if maps[i][0] and dp[i-1][0]:
dp[i][0] = 1
for i in range(1,n):
for j in range(1,m):
if maps[i][j]:
dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007
return dp[-1][-1]