analyse thought process — 2477. Minimum Fuel Cost to Report to the Capital

Answer

• what happened
• what went right
• what went wrong
• what can i learn from it
• one thing i’ll do different

* what happened

I started to solve: 2477. Minimum Fuel Cost to Report to the Capital

It is a medium question with a dynamic programming tag and bonus points because it is a tree problem; I wanted to do a tree dynamic programming problem for a while because I have never done it before

Initially, I drew a tree for a couple of inputs to see their expected result to understand how an algorithm should behave.

If a problem branches out so much, it feels like complexity skyrockets; I noticed that we have many combinations on a branch of 6 nodes and 2 seats.

That is the case where we greedily fill the car as soon as possible, and once the car is full, we add a new car.

What if we fill up the car in some city after?

The result appears to be the same, but should I verify that it always will be the same? How many such combinations may come up? What when there are more seats? How can I be sure that greedy decision to pick up each person as I go is correct?

Then I drew one example to see how it would work with 1, 2, and 3 seats; what pattern for seat number can I spot?

Suddenly I had an idea that these problems are similar and thought about the statement that dynamic programming is about breaking down a complex problem into overlapping subproblems so we can memoize overlapping subproblems.

I noticed that even in cases of N branches from the capital, we repeat the same process for each branch and that the fuel cost is a sum of costs for each branch if we have a tree.

The fuel cost is:

This led me to believe that solution might look like this:

Or something like that. Since that is a tree, I don’t know if that’s good, possible, or if I even should approach a solution like that.

Since I have no idea about that, maybe I should read up more on tree strategies, so the next time I know what an optimal way to operate with tree branching algorithms is

By the end, I cheated and found that the solution may create a tree, then used a depth-first search to calculate the fuel cost to reach the capital. However, I am eager to find a dynamic programming solution.

* what went right

In the past, I didn’t know:

• how to implement recursion
• how to spot opportunities for recursion
• how to think to find a recursive solution
• how to write a recursive solution once I figure out the solution

Now:

• I can’t decide on the correct approach
• I can’t decide which approach is better
• I didn’t consider approaches I could use BEFORE DECIDING TO USE DP; for example, a tree algorithm might have been a faster solution than DP

The great thing is that I had a lot of exploration space on my own, while my exploration was suboptimal and didn’t lead me to the solution.

* what went wrong

I take a problem and solve it for the sake of solving it; I simply explore as widely and as deeply as possible without considering the time I’m spending on the problem.

Such an approach is good for improvement, and it lacks the focus on the results.

* what can I learn from it

I should consider practicing both the optimality of searching for solutions and expanding my knowledge and skills.

Learning from widening the search gives a lot of insights, and I should apply those, then practice to improve and ingrain them into my skills.

* one thing I’ll do different

I don’t know :D Maybe I’ll figure it out later.