언급한 풀이  <<- 주소 입니다.

스스로 문제를 풀어본 뒤, 다른 분들 코드를 보았는데 시간복잡도나 공간복잡도가 굉장히 차이가 나더군요. 따라서 배울 점이 많은 것 같아 참고하며 공부하려 하였습니다.

그런데 문득, 윗 분의 코드가 dp라는 범주에 포함되는지 궁금해졌습니다. (코드에 대한 이해는 하였습니다.)

저는 DP의 정의를 "주어진 문제를 나누어 풀고, 그 결과를 이용하여 주어진 문제를 해결한다"라고 알고 있는데, 이러한 풀이도 DP에 해당하는 지 알고 싶습니다. 

제가 위 코드가 DP문제인지 햇갈리는 이유는 다음과 같습니다.

1. 문제를 나누어 푼다는 것을 저는 주어진 조건인 (w,v)에 따라 나누어 푼다고 생각하는데 위 코드는 하나의 변수로만 나누어 해결하셨습니다.

(조건을 w 하나로 축소시켜 해결하였다고 봐야할까요..?)

2. 위 코드에서, dp[]가 for문을 돌면서 계속 갱신이 되는데, 이러한 경우는 아직까지 만나보지 못하였습니다.

dp가 정의하기 애매한 부분이 있는건지, 아니면 dp가 여러가지 종류가 있고, 제가 아직 그러한 종류를 배우지 못하여 모르는 건지 또 아니라면 dp는 아니지만 또다른 알고리즘을 이용하였다고 보아야 하는지 궁금합니다.