I think these examples show some missing requirements in the set of problems suitable for dynamic programming. Primarily, that the sub-problems must be very similar to the main problem, such that the same solution applies to them.
DP is nothing more than recursion + memoization. Recursion is solving a problem by breaking it into a trivial combination of smaller problems, and repeating that process until the smallest problem is itself trivial so you don’t need to break it down further. Memoization is just remembering the results of previous sub-problems, because you’ll often need them multiple times.
The OP misses out on the first step: defining the problem, and skips to the second, adding up the results. DP is a way to notice that you’ll have to solve it in reverse, but you still approach it forward. You write the code that knows the best way from a node to Boston is the lowest sum of “cost to next node” and “cost of THAT node to boston”. So Miami’s best choice is the lowest of 200+A->Boston or 170+B->Boston. We don’t know either of those sub-values yet, but we know how to calculate them—the exact same way, the lower of cost-of-path+cost-of-node-to-Boston. Until we’re one away from Boston, then it’s just cost-of-path-to-Boston.
In setting up this problem this way, it becomes clear that we’re performing calculations backwards from Boston, but we don’t need to figure that out specifically, it’s built into the nature of DP.
I think these examples show some missing requirements in the set of problems suitable for dynamic programming. Primarily, that the sub-problems must be very similar to the main problem, such that the same solution applies to them.
DP is nothing more than recursion + memoization. Recursion is solving a problem by breaking it into a trivial combination of smaller problems, and repeating that process until the smallest problem is itself trivial so you don’t need to break it down further. Memoization is just remembering the results of previous sub-problems, because you’ll often need them multiple times.
The OP misses out on the first step: defining the problem, and skips to the second, adding up the results. DP is a way to notice that you’ll have to solve it in reverse, but you still approach it forward. You write the code that knows the best way from a node to Boston is the lowest sum of “cost to next node” and “cost of THAT node to boston”. So Miami’s best choice is the lowest of 200+A->Boston or 170+B->Boston. We don’t know either of those sub-values yet, but we know how to calculate them—the exact same way, the lower of cost-of-path+cost-of-node-to-Boston. Until we’re one away from Boston, then it’s just cost-of-path-to-Boston.
In setting up this problem this way, it becomes clear that we’re performing calculations backwards from Boston, but we don’t need to figure that out specifically, it’s built into the nature of DP.