Dynamic Programming Basic example

DP_stair_factorial.js

// http://www.csie.ntnu.edu.tw/~u91029/DynamicProgramming.html#2

function stairs(n) {
  var res = [];
  res[0] = 1; // first stair
  res[1] = 1; // second stair

  if (n > 0 && n < 2) return res[n-1];

  for (var i = 2; i < n; i++){
    res[i] = res[i-1] + res[i-2];  // linear space
  }
  return res[n-1];
}

console.log(stairs(1));   // 1
console.log(stairs(2));   // 1
console.log(stairs(5));   // 5



function factorial(x) {
  var res = [];
  res[0] = 1;
  res[1] = 1;

  if (x >= 0 && x < 2) return res[x];

  for (var i = 2; i < x+1; i++){
    res[i] = res[i-1] * i;
  }
  return res[x];
}

console.log(factorial(0));   // 1
console.log(factorial(1));   // 1
console.log(factorial(5));   // 120
console.log(factorial(7));   // 5040
console.log(factorial(10));   // 3628800