Hello Everyone!
This is the last post of Week 9 and I ended with Multidimensional Dynamic Programming. The challenges were interesting and fun, but at the same time pushed me into thinking in grids and systematic aspects of optimization. That way, it felt like tackling a well thought out puzzle, where every move made counted.
How the Day Went
-
Walking Optimization Minimum Path Sum (Medium Difficulty)
The problem was to discover which path from the upper left corner to the bottom right corner has the least total distance.- My Approach: Applied the concept of Dynamic programming where each cell stored the minimum sum to get that particular cell. Determined the value at every cell as the addition of the current value to the minimum of the value from the cell either above or to the left of the cell.
- What I Enjoyed: To be able to follow each step of the calculation and watch the grid turn from one to the other and reach the solution was very fulfilling. The paper was an accurate feeling of driving through the city, pronoucing noticeable coincidegences, and plotting the best course simultaneously.
-
Medium – Unique Paths II
It was important to quantify the number of paths where it is possible to move and reach a goal tile at the end-bottom right corner while passing through the cells free from obstacles.- My Approach: Modified the original approach for the unique path problem using dynamic programming by assigning cells with obstacles a value of `0’ that prohibits path to them. Differentiated for each cell the number of paths which can be traced from it considering paths of neighbouring cells from above and on the left-hand side are blocked.
- What I Enjoyed: Challenges posed to the problem added another dimension into the problem handling. Solving it was more like approaching a maze in which some paths are blocked.
Why Today Stood Out
Dynamic Problem Solving:
Both problems highlighted the importance of structure to perform well with respects to dynamic programming techniques that had to be optimally adapted to solve them.Clear Visuals Helped:
When solving problems using the grid, and observing the solutions come to life, it was practical and beneficial.Practical Scenarios:
– These challenges were practical; for instance, there was route optimization, and constraints management, which made the experience as realistic as possible.
Key Lessons Learned
Dynamic Programming is a Game-Changer:
Dividing problems into several sub-problems that are dependent on each other as in Minimum Path Sum makes complex work easier.Adaptability is Critical:
Inserting deviations in standard approaches, as was done in Unique Paths II, is also an excellent way to show how adaptability plays a role in problem-solving.Layer-by-Layer Thinking Works:
Addressing solutions in progressive manner, layer by layer, keeps things well-defined and eliminates the excess ballast.
Reflections
This week, the Minimum Path Sum was a great practice in approaching grid and trying to find the shortest path while obtaining the optimal solution Unique Paths II added an interesting wrinkle by including obstacles. Both a problems enhanced knowledge of multidimensional dynamic programming as essential to multidimensional dynamic programming and illustrated a variety of applications of this technique to real-world problems.
Looking Ahead
With Week 9 being over or done, I can prepare for Week 10. I will then move to the topic of Greedy Algorithms, Advanced Graph Problems and the Dynamic Programming section and All. What I’m looking forward to?
Well, that’s the story of my life so far or at least the parts to which I was able to put words into. Let’s continue working on solving processes, enhancing and changing for the better, and the expanding in unity.
Top comments (0)