You can solve this problem filling the following table.
Let's say that $cost(row,col)$ is the minimal cost that can be achieved starting from one node on the leftmost edge of the grid and ending in the cell $(row, col)$, only performing valid operations.
The answer to the problem will be the minimum among all $cost(i,j)$ where $j=last\_col$. Notice that table $cost$ table is the same as $opt$ table, but now you have the proper semantic of it's entries, so it's easy to fill base values, and extract final values.
- Step 1:
Base values: Fill first column entries with there current value. i.e $cost(i,j)$ where $j=0$. It is $cost(i,0)=value(i,0)$ since the only way you can reach node $(i,0)$ starting in a leftmost node and performing valid operation, is starting in the node itself.
- Step 2:
The same you described before. This holds, because you can only get nodes on the $j^{th}$ column from the $(j-1)^{th}$ column, and since you are filling $cost$ table in increasing order of columns, previous values will be computed when you need to compute current values. [This is dynamic programming]
- Step 3:
As I said before, and you said too, return the minimal value among all entries in the last column of $cost$ table.
Why Bellman Ford (BF) works here in the way you do it.
BF algorithm finds shortest path in a graph from a single source to every other node inside the graph. In the $k^{th}$ step BF have already computed shortest path starting from source node $S$ to every other node using at most $k$ edges.
Let's transform our problem into a valid instance for BF, and the let's modify BF to run in $O(n^2)$.
Let's say we convert each cell of the grid into a node, and you put an edge between node $u$ and $v$ if the transition from $u$ and $v$ is valid. Let the cost of edge between $u-v$ be the original cost of the cell $v$, so moving through this edge adds to the overall cost getting into node $v$, as we expect.
Now we have two problems.
- Problem 1, the running time of our algorithm will be $O(nodes \cdot edges)$ where $nodes$ is $n^2$ and $edges$ is $O(nodes) = O(n^2)$ so overall complexity will be $O(n^4)$.
- Problem 2. There are several sources, so we need to run BF starting at every source, and this increase the overall complexity by a factor of $n$.
Let's get rid of both problems, starting from problem 2. If you add an extra node connected to every node at the first column, you simulate the process of starting at every node in one run. Look at the following image for more understanding. I didn't pain all connection but just a few.
To get rid of the first problem, you need to exploit the structure of our graph. It is not so general. You can only reach nodes in the $k^{th}$ column in the $k^{th}$ step, and since there is no backward edge, in this step only nodes in this column needs to be updated. So overall complexity will be $O(nodes) = O(n^2)$.
