[알고리즘] DP문제에서 Top-down과 Bottom-up 어떻게 판단할까?
Top-down vs Bottom-up
DP문제를 풀 때 항상 고민하는 것은 'Top-down으로 풀어야하나 Bottom-up으로 풀어야하나' 이다. 그래서 다른 개발자들은 어떻게 접근하는지 참고해보자.
Top-down은 언제 사용하는게 좋을까?
→ Generally, I recommend the top-down solution when either of the following is true:
- It's not easy to see in what order the sub-problems should be solved if you were going to solve them bottom-up. This is sometimes the case if the relationship between the sub-problems is complicated.
- It's possible that only a small number of sub-problems will be used as part of the solution. For example, the answer to your problem is F(k) and F(0) is the base case, but you're not sure that you need to know every value between F(0)...F(k) to solve the problem.
- 당연한 말이지만 되새길만 하다. 바텀업으로 푸는데 서브문제가 잘 풀리지 않는다면 (서브문제끼리의 관계가 복잡하다면) 탑다운방식으로 접근해라.
- 서브 문제 전체의 크기에 비해 메인 문제에 관여하는 수가 적을 때 (예로, F(n)을 푸는데 F(n-1) ~ F(0) 부분만 사용할 때) 탑다운으로 접근해라
☛ 여러 글들을 종합해본 결과 DP 풀이 접근 방식은 Top-down이 자연스럽게 접근이 가능하다.
☛ 하지만! 효율성을 고려해야할 경우는 Bottom-up이 더 좋다.
☛ 그리고 하위문제가 복잡하여 점화식으로 풀어낼 방법이 떠오르지 않을 경우 Top-down으로 많이 접근한다고 한다.
참고 글
What is the difference between bottom-up and top-down?
The bottom-up approach (to dynamic programming) consists in first looking at the "smaller" subproblems, and then solve the larger subproblems using the solution to the smaller problems. The top-down
stackoverflow.com
Can every problem on Dynamic Programming be solved by both top-down and bottom-up approaches?
Answer (1 of 5): Generally, I recommend the top-down solution when either of the following is true: 1. It's not easy to see in what order the sub-problems should be solved if you were going to solve them bottom-up. This is sometimes the case if the relatio
www.quora.com