Memoization

Top-down

Bottom-up

Devide and conquer

막대기자르기

var p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30];
function cutRod(p, n) {
  var r = [0];
  for (var j = 1; j <= n; j++) {
    q = -1;
    for (var i = 1; i <= j; i++) {
      q = Math.max(q, p[i] + r[j - i]);
    }
    r[j] = q;
  }
  return r[n];
}
cutRod(p, 2); // 5
cutRod(p, 3); // 8
cutRod(p, 4); // 10
cutRod(p, 7); // 18

최장 공통 부분 수열 문제

function LCS(x, y) {
  var i = x.length;
  var j = y.length;
  var result = [];
  for (var k = 0; k <= i; k++) {
    if (!result[k]) {
      result[k] = []; // 이전 계산 값 저장 공간
    }
  }
  for (k = 0; k <= i; k++) {
    for (var l = 0; l <= j; l++) {
      console.log(k, l);
      if (k === 0 || l === 0) { // 베이스 값 설정
        result[k][l] = 0;
      } else if (x[k - 1] === y[l - 1]) { // 마지막 두 문자 비교, 같으면
        result[k][l] = result[k - 1][l - 1] + 1;
      } else { // 마지막 두 문자가 다르면
        result[k][l] = Math.max(result[k - 1][l], result[k][l - 1]);
      }
    }
  }
  return result[i][j];
}
LCS('ABCBDAB', 'BDCABA'); // 4

0/1 배낭 문제

var item = [[1, 60, 10], [2, 100, 20], [3, 120, 30]];
function zeroOneKnapsack(item, cap) {
  var m = [];
  for (var i = 0; i <= item.length; i++) {
    m[i] = [];
  }
  for (i = 0; i < item.length + 1; i++) {
    for (var j = 0; j <= cap; j++) {
      if (i === 0 || j === 0) { // 물건이나 무게가 없음
        m[i][j] = 0;
      } else if (item[i-1][2] > j) { // 물건의 무게가 j보다 크면
        m[i][j] = m[i-1][j];
      } else {
        m[i][j] = Math.max(m[i-1][j], m[i-1][j-item[i-1][2]] + item[i-1][1]);
      }
    }
  }
  return m[item.length][cap];
}
zeroOneKnapsack(item, 50); // 220