Please enable JavaScript.

Coggle requires JavaScript to display documents.

Dynamic Programming - Coggle Diagram

- - - - F (i, j ) = max{F (i − 1, j ), F (i, j − 1)} + cij for 1 ≤ i ≤ n, 1 ≤ j ≤ m
        F (0, j) = 0 for 1 ≤ j ≤ m and F (i, 0) = 0 for 1 ≤ i ≤ n,
      - ALGORITHM RobotCoinCollection(C[1..n, 1..m]) :
        //Applies dynamic programming to compute the largest number of coins a robot can collect on an n × m board by starting at (1, 1)
        and moving right and down from upper left to down right corner
        //Input: Matrix C[1..n, 1..m] whose elements are equal to 1 and 0 for cells with and without a coin, respectively
        //Output: Largest number of coins the robot can bring to cell (n, m)
        F[1, 1]← C[1, 1]; for j ← 2 to m do F[1, j ]← F[1, j − 1] + C[1, j ] for i ← 2 to n do
        F[i, 1]← F[i − 1, 1] + C[i, 1]
        for j ← 2 to m do
        F[i, j ]← max(F[i − 1, j ], F[i, j − 1]) + C[i, j ]
        return F[n, m]
  - - - F (n) = max{cn + F (n − 2), F (n − 1)} for n > 1,
        F (0) = 0, F(1) = c1.
      - ALGORITHM: CoinRow(C[1..n])
        //Applies formula (8.3) bottom up to find the maximum amount of money that can be picked up from a coin row without picking two adjacent coins
        //Input: Array C[1..n] of positive integers indicating the coin values
        //Output: The maximum amount of money that can be picked up
        F[0]← 0; F[1]← C[1]
        for i ← 2 to n do{
        F[i]← max(C[i] + F[i − 2], F[i− 1])
        }
        return F[n]
  - - - F (n) = min j : n≥dj {F (n − dj )} + 1 for n > 0, F (0) = 0.
      - ALGORITHM :ChangeMaking(D[1..m], n)
        //Applies dynamic programming to find the minimum number of coins //of denominations d1 < d2 < ... < dm where d1 = 1 that add up to a //given amount n
        //Input: Positive integer n and array D[1..m] of increasing positive integers indicating the coin denominations where D[1] = 1
        //Output: The minimum number of coins that add up to n
        F[0]← 0
        for i ← 1 to n do
        temp ← ∞; j ← 1
        while j ≤ m and i ≥ D[j ] do
        temp ← min(F[i − D[j ]], temp)
        j ← j + 1
        F[i]← temp + 1
        return F[n]
- - - - One variation of the dynamic programming approach seeks to avoid solving unnecessary subproblems.
        
        This technique, exploits so-called memory functions and can be considered a top-down variation of dynamic programming.
      - Since a majority of dynamic programming applications deal with optimization problems, we also need to mention a general principle that underlines such
        applications
        
        principle of optimality
        
        It says that an optimal solution to any
        instance of an optimization problem is composed of optimal solutions to its subinstances.