Completing a degree. How do I get a degree in X? Get an A in the classes required for X. What do I do to get an A in those classes? Get an A on the assignments for each class. What do I do to get an A on those assignments? Solve each problem on the assignment. What do I do to solve the problems? Perform each calculation correctly. How do I perform each calculation? Understand the underlying material correctly. How do I understand the underlying material correctly? Understand the individual statements that build up into the explanation correctly...
Building a fence. How do I design a fence? By designing the components: the panels, posts, and gate. How do I design the components? By designing the subcomponents: the frame, paneling, and joints. How do I design the subcomponents? By designing the sub-subcomponents: the cuts, nails/screws, dimensions, and materials.
Making a friend. How do I make a friend? By getting to know an acquaintance better. How do I make an acquaintance? By getting to know a stranger better. How do I meet a stranger? By getting to know my social surroundings better.
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.
Completing a degree. How do I get a degree in X? Get an A in the classes required for X. What do I do to get an A in those classes? Get an A on the assignments for each class. What do I do to get an A on those assignments? Solve each problem on the assignment. What do I do to solve the problems? Perform each calculation correctly. How do I perform each calculation? Understand the underlying material correctly. How do I understand the underlying material correctly? Understand the individual statements that build up into the explanation correctly...
Building a fence. How do I design a fence? By designing the components: the panels, posts, and gate. How do I design the components? By designing the subcomponents: the frame, paneling, and joints. How do I design the subcomponents? By designing the sub-subcomponents: the cuts, nails/screws, dimensions, and materials.
Making a friend. How do I make a friend? By getting to know an acquaintance better. How do I make an acquaintance? By getting to know a stranger better. How do I meet a stranger? By getting to know my social surroundings better.
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.