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 wants to do. It was interesting seeing how cleanly the logic works when written out step by step.
Floyd’s algorithm ended up being my favorite. It’s one of those algorithms where you can really see recursion and dynamic programming working together. Watching the matrix update as each intermediate vertex is considered made the whole process feel intuitive. It’s satisfying to see how the shortest paths emerge from what looks like a simple triple loop.

Overall, this week was a mix of challenge and clarity. Some parts clicked immediately while others took repetition and patience, but by the end I felt like I actually understood how these algorithms build solutions from smaller subproblems.