DP (dynamic programming : 동적 계획법)

핵심 포인트

재귀 또는 귀납법을 이용할 때 이미 구했던 값은 또 구하지 않기 (구한 값은 저장할 것)

 

동적계획법 문제인지 확인하는 법

1. 배열을 이용하여 문제를 풀 때 배열의 i번째 인덱스의 값이 중복해서 사용될 경우

2. 특정 알고리즘을 이용해서 푸는 방식이 아닌 피보나치 수열과 같은 방식으로 풀릴 때

( dp[i]=dp[i-1]+dp[i-2] 공식으로 풀린다면 for문에 i=1이면 dp[0]을 사용하고 i=2일때도 dp[0]을 사용한다. )

 

-> 구한 값들은 dp배열을 따로 만들어서 i번째 인덱스에 저장 후 반복 사용