Counting is not optimising

Two questions about the same grid of blocked and open cells:

1. 1What is the cheapest route from corner to corner?
2. 2How many routes are there?

They use the same table and differ in one operator.

cheapest:   best[i][j] = cost[i][j] + min(best[i-1][j], best[i][j-1])
counting:   ways[i][j] =             ways[i-1][j] + ways[i][j-1]

min becomes +. That is the entire difference.

Why it is worth naming

Recognising which one you are being asked matters more than it sounds, because the two have different traps.

Optimising questions need optimal substructure, which you should check.

Counting questions usually do not fit in a normal integer. A clear 20 by 20 grid has about 137 billion routes; a 100 by 100 grid has a number with 58 digits. Which is why counting problems so often end with "give the answer modulo 1000000007": the modulus is there to keep the arithmetic in range, not to make the problem harder.

The base case is where counting goes wrong

For a cheapest-route table, an unreachable cell is infinity. For a counting table it is zero, and the start is one, not zero. Setting the start to zero gives an answer of zero everywhere, which looks like a broken table and is actually a base case saying there are no ways to be where you started.

The third variant

Some problems ask which rather than how many or how cheap, meaning list the actual routes. That is not dynamic programming, because the output itself is exponential. It is backtracking, and the giveaway is a small bound such as n <= 12.