CST-370 Week 7
This week, I learned about Dynamic programming, which is algorithm design technique for improving the efficiency of certain recursive algorithms, such as Warshall's algorithm and Floyd's algorithm. I also learned about the Greedy technique, which is used to solve optimization problems, such as the Prim algorithm Dynamic Programming To avoid multiple calls for a sub-problem (ex: base case for fib), use an array to keep solutions of sub-problems. Example: Fib(n): F[0] = 0; F[1] = 1; for (i = 2 to n): F[i] = F[i-1] + F[i-2] return F[n]; In General: 1. Set up a recurrence relation that describes a solution to a problem with smaller sub-problems. 2. Solve the smaller sub-problems and record the solutions in a table. 3. Solve the original problem using the table. Dynamic Programming - Solving Coin-Row Problem Coin-row problem: There is a row of n coin...