[일반] dp 공부하면서 생각난건데 이거맞음?

[익명(61.76)]

모든 dp문제는 재귀 or 반복문에서 메모이제이션이 추가된것

메모리를 더먹는대신 속도가 더 빨라졌을뿐이고

모든 재귀(스도쿠나 nqueen같은 백트래킹등)문제에서 메모이제이션만 추가되면  dp문제가 될수있는건가?

[익명(118.235)]

dp는 메모이제이션과 다른거임. dp는 문제를 부분문제로 나누어서 푸는 것이고 메모이제이션은 중복처리를 빠르게 하는 기법. 일반 백트래킹은 중복이 없어서 의미가 없음

[익명(61.76)]

내가 잘못알고있었네 ㄱㅅㄱㅅ

[익명(183.100)]

그렇게만 설명하면 분할정복이랑 헷갈릴듯 dp랑 분할정복이랑 문제를 부분으로 나누는건 동일한데 dp는 하위문제들이 중복되어 그 값을 일반적으로 메모이제이션 기법을 사용해서 불필요한 계산을 안하는거고 분할정복은 서로 중복되지 않고 전체를 부분으로 나눠 그 부분으로 부터 정답을 도출해내는거임

[익명(61.76)]

고맙다 이제 진짜 구분할수있겠다ㄱㅅㄱㅅ

[익명(211.36)]

대략적으로 그런느낌이긴 한데 모든 이라 일반화하기에는 무리가 있지 그리고 시간 메모리 줄이는건 둘다 줄일때도 많은듯