CST370 - WEEK 7
This week’s material focused on dynamic programming. We started with the classic Fibonacci example, which shows why dynamic programming matters in the first place. Instead of making multiple calls to the same subproblem, we store results in an array and reuse them. This is to avoid repeated work and build solutions from smaller subproblems. We went over the coin‑row problem, which is picking up the maximum number of coins along a path. This concept was definitely the hardest one for me. I kept thinking I was doing the right thing, only to realize I misunderstood how the subproblems connected. I redid the practice problems so many times and eventually the pattern clicked. It was frustrating but also satisfying once I finally saw how the DP table grows and how the path is reconstructed. Warshall’s algorithm for transitive closure felt much more straightforward. Once you look at the matrix, you can almost see the solution forming. The algorithm just formalizes what your brain already want...
