Dynamic programming

Dynamic-Programming.md

Dynamic Programming

Jamie Long

Efficiency is key.

A technique for producing 'fast' algoristhms for solving kinds of 'slow' recusive sollutions.

Useful when:

Optimal substructure. Solution can be derived by calculating the solutions to subprobl;ems. Overlapping subproblems. Subproblem solutions can be reused.

Start off by solving simple subproblems. use the solution to derive solutions for slightly larger sets. Then larger sets..

caching is key to storing the solution to the subproblem.

Google facebook Amazon Apple

Top down memoization is the other way to do it.

dynamic is bottom up.

Bottom up dynamic programming

How to do it:

Initialize an array

function initializeArray(n, fillChar = undefined) {
  const result = []


}

Initialize Matrix

fucntion initializeMatrix(m, n, fillChar = undefined) {
  const result = [];
  
  for (let i = 0; i < m; i++) {
    result.push(initializeArray(n, fillChar));
  }
  
  return result;
}

if all inputs are integers.

function fib(n) {
  const cache = initializeArray(n + 1)

cache[0] = 1;
cache[1] = 1;

  for (let i = 2; i <= n; i++) {
    cache[i] = cache[i - 1] + cache[i - 2];
  }
}

Robot paths

function pathsCount(m, n) {
  const cache = initializeMatrix(m, n);
  
  for (let i = 0; i < m; i++) {
    cache[i][0] = 1;
  }
  
  for (let j = 0; j < n; j++) {
    cache[0]][j] = 1;
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      cache[1][j] = cache[i - 1][j] + cache[i][j - 1];
    }
  }
}