다이나믹 프로그래밍 문제를 풀때, Top-Down, Bottom-Up 어떤 문제에도 둘 다 사용 가능하나요?

Question

다이나믹 프로그래밍을 공부중인데 Top-Bottom으로 푼 문제 A가 있습니다.근데 문제를 푸는 방식이 Top-Down, Bottom-Up 두 가지가 있으니까 두 가지 다 풀어보고 싶은데Top-Down은 되지만 Bottom-Up은 안 되는 문제가 있고, 그 반대도 있습니다.그냥 제가 아직 익숙하지 않아서 안 풀리지 모르겠습니다.

엡실론 · Answer

조금 덜 효율적일 수는 있으나 불가능한 경우는 없을 것 같네요. 예제를 올려보세요.

후드캣 · Answer

https://www.acmicpc.net/problem/10844 위의 링크가 문제입니다. using System; using static System.Console; public class main { static long[,] dp; static void Main() { int n &#61; Convert.ToInt32(ReadLine()); dp &#61; new long[n&#43;1, 10]; long answer &#61; 0; for(int i &#61; 1; i <&#61; 9; i&#43;&#43;) { answer &#43;&#61; (StairsNum(n, i) % 1000000000); } WriteLine(answer % 1000000000); } static long StairsNum(int digit, int numValue) { if(digit &#61;&#61; 1) return 1; if(dp[digit, numValue] !&#61; 0) return dp[digit, numValue]; if(numValue &#61;&#61; 9) dp[digit, numValue] &#61; StairsNum(digit-1, 8) % 1000000000; else if(numValue &#61;&#61; 0) dp[digit, numValue] &#61; StairsNum(digit-1, 1) % 1000000000; else dp[digit, numValue] &#61; (StairsNum(digit-1, numValue-1) % 1000000000 &#43; StairsNum(digit-1, numValue&#43;1) % 1000000000) % 1000000000; return dp[digit, numValue]; } }이게 제가 Top-Down으로 푼 문제입니다. 재귀를 사용하지 않고 Bottom-Up 방식을 해보고는 싶었는데..잘 안 되는 거 같습니다.

다이나믹 프로그래밍 문제를 풀때, Top-Down, Bottom-Up 어떤 문제에도 둘 다 사용 가능하나요?

2개의 답변

#dp 목록