| [ QuizWit ] in KIDS 글 쓴 이(By): guest (aseg) <211.177.254.29> 날 짜 (Date): 2003년 7월 5일 토요일 오전 03시 58분 09초 제 목(Title): Re: what f* is? Dynamic programming is just like filling an array whose dimension depends on different problems. For example, let's say that you have a function f, defined as for all x, f(0,x) = 0, f(x,0) = 0 and f(x,y) = f(x-1,y) + f(x,y-1) + 1 As you see, f is a recursive function. Only recursive functions can be solved with dynamic programming but not all the recursive functions can be solved with it. Now, let's say that you want to evaluate f(5,5). Maybe you have two choices. One clear way is: (1) whenever you need to evaluate f with some arguments, you solve it in a recursive fashion: to evaluate f(5,5), you need to evaluate f(4,5) and f(5,4). to evaluate f(4,5), you need to evaluate f(3,5) and f(4,4). to evaluate f(5,4), you need to evaluate f(4,4) and f(5,3). ....etc you see some duplication? you must evaluate f(4,4) twice! this is no effective. Dynamic programming removes such duplications: (2) fill a 2nd dimension array, starting with base cases: First you construct 6x6 array then you fill (0,x) and (x,0) with 0 for all x. If the left and upper ones of a cell are filled, you can fill it: (1,0) and (0,1) are already filled so you can fill (1,1). just like this, you can fill (2,1) because you already had (1,1) and (2,0) filled. just in the same way, you can fill (3,1), (4,1) and (5,1). then you go 1 column right, and do the same thing again. Repeat it until you get at (5,5). then you will finally fill (5,5), which is f(5,5). there is no duplication and as you can see, you have filled only necessary cells and only once for each. in other words, you've done the minimal calculations to get f(5,5). This technic is what we call dynamic programming. |