Please enable JavaScript.
Coggle requires JavaScript to display documents.
Dynamic Programming - Coggle Diagram
Dynamic Programming
Three Basic Examples
-
Coin-collecting Problem
A robot, located in the upper left cell of the board, needs to collect as many of the coins as possible and bring them to the bottom right cell. On each step, the robot can move either one cell to the right or one cell down from its current location. Find the maximum number of coins the robot can collect.
Coin-row Problem
The goal is to pick up the maximum amount of money subject to the constraint that no two coins adjacent in the initial row can be picked up.
Knapsack Problem
given n items of known weights w1, . . . , w n and values v1, . . . , v n and a knapsack of capacity W , find the most valuable subset of the items that fit into the knapsack.
Memory functions
Solves a given problem in the top-down manner and maintains a table that is used by a bottom-up dynamic programming algorithm, initializes the table with NULL and whenever the value is NULL, calculates the expression, otherwise, uses its result.
-
-
-
-
is a technique for solving problems with overlapping subproblems, instead of the subproblems again and again, what we do is we solve the subproblem once and saves in an array