DynamicProgramming

动态规划

• 核心

  • canSum –> Decision Problem
  • howSum –> Combinatoric Problem
  • bestSum –> Optimization Problem

• 技巧

  • Memoization(缓存)
  • Tabulation(制表)
    • visualize the problem as a table
    • size the table based on the inputs
    • initialize the table with default values
    • seed the trivial answer into the table
    • iterate through the table
    • fill futher positions based on the current position

• 应用

  • Fibnacci
  • gridTraveler
  • TargetSum
    • canSum
    • howSum
    • bestSum
  • Construct
    • canConstruct
    • countConstruct
    • allConstruct

应用实现

斐波那契

• 代码实现

const fib = (n) => {
    const table = Array(n + 1).fill(0);
    table[1] = 1;
    for (let i = 0; i <= n; i++) {
        table[i + 1] += table[i];
        table[i + 2] += table[i];
    }
    return table[n];
};

console.log(fib(6)); //8
console.log(fib(7)); //13
console.log(fib(8)); //21
console.log(fib(50)); //12586269025

网格旅行者

• 代码实现

const gridTraveler = (m, n) => {
    const table = Array(m + 1)
        // .fill(Array(n + 1));
        .fill()
        .map(() => Array(n + 1).fill(0));
    table[1][1] = 1;

    for (let i = 0; i <= m; i++) {
        for (let j = 0; j <= n; j++) {
            const current = table[i][j];
            if (i + 1 <= m) table[i + 1][j] += current;
            if (j + 1 <= n) table[i][j + 1] += current;
        }
    }
    return table[m][n];
}

console.log(gridTraveler(1,1)); //1
console.log(gridTraveler(2,3)); //3
console.log(gridTraveler(3, 2)); //3
console.log(gridTraveler(3,3)); //6
console.log(gridTraveler(18,18)); //2333606220

canSum

代码实现

const canSum = (targetSum,numbers) => {
  const table = Array(targetSum + 1).fill(false);
  table[0] = true;
  // for (let i = 0;i < table.length;i++){
  for (let i = 0;i <= targetSum;i++){
      if (table[i] === true){
          for (let num of numbers){
              table[i + num] = true;
          }
      }
  }
  return table[targetSum];
};

console.log(canSum(7,[2,3]));   //true
console.log(canSum(7,[5,3,4,7])); //true
console.log(canSum(7,[2,4]));   //false
console.log(canSum(8,[2,3,5])); //true
console.log(canSum(300,[7,14])); //false

//Decision problem

howSum

Write a function howSum(targetSum,numbers) that takes in a targetSum and an array of numbers as arguments

The function should return an array containing any combination of elements that add up to exactly the targetSum

If there is no combination that add up to the targetSum,then return null

代码实现

const howSum = (targetSum, numbers) => {
  const table = Array(targetSum + 1).fill(null);
  table[0] = [];
  for (let i = 0;i <= targetSum;i++){
      if (table[i] !== null){
          for (let num of numbers){
              table[i + num] = [...table[i],num];

          }
      }
  }
  return table[targetSum];
};

console.log(howSum(7,[2,3]));   //[ 3, 2, 2 ]
console.log(howSum(7,[5,3,4,7])); //[ 4, 3 ]
console.log(howSum(7,[2,4]));   //null
console.log(howSum(8,[2,3,5])); //[ 2, 2, 2, 2 ]
console.log(howSum(300,[7,14])); //null

//Combinatoric problem

bestSum

代码实现

• 制表法

const bestSum = (targetSum, numbers) => {
    const table = Array(targetSum + 1).fill(null);
    table[0] = [];
    for (let i = 0; i <= targetSum; i++) {
        if (table[i] !== null) {
            for (let num of numbers) {
                const combination = [...table[i], num];
                //如果当前组合数组更短,便将它存储
                if (!table[i + num] || table[i + num].length > combination.length) {
                    table[i + num] = combination;
                }
            }
        }
    }
    return table[targetSum];
};
//Memoization
console.log(bestSum(7, [2, 3]));   //[ 2, 2, 3 ]
console.log(bestSum(7, [5, 3, 4, 7])); // [ 7 ]
console.log(bestSum(7, [2, 4]));   //null
console.log(bestSum(8, [2, 3, 5])); // [ 3, 5 ]
console.log(bestSum(300, [7, 14])); //null

canConstruct

代码实现

• Memoization

const canConstruct = (target, workBank,memo = {}) => {
    if (target in memo) return memo[target];
    if (target === '') {
        return true;
    }
    for (let word of workBank){
        if (target.indexOf(word) === 0){
            const suffix = target.slice(word.length);
           if (canConstruct(suffix,workBank,memo) === true){
               memo[target] = true;
               return true;
           }
        }
    }
    memo[target] = false;
    return false;
};
// m = target.length
// n = array.length
console.log(canConstruct("abcdef",["ab","abc","cd","def","abcd"]))  //true
console.log(canConstruct("skateboard",["bo","rd","ate","t","ska","sk","boar"]));    //false
console.log(canConstruct("enterapotentpot",["a","p","ent","enter","ot","o","t"]));  //true
console.log(canConstruct("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef",[
    "e",
    "ee",
    "eee",
    "eeee",
    "eeeee",
    "eeeeee",
    "eeeeeee"
]));    // false

// brute force
//time O(n ^ m * m)
//space O(m)

// memoized
//time O(n * m * m) = O(n * m ^ 2)
//space O(m ^ 2)

• Tabulation

const canConstruct = (target, workBank) => {
    const table = Array(target.length + 1).fill(false);
    table[0] = true;


    for (let i = 0;i <= target.length;i++){
        if (table[i] === true){
            for (let word of workBank){
                // 检查当前的单词是否与从索引i开始的字符匹配
                if (target.slice(i,i + word.length) === word){
                    table[i + word.length] = true;
                }
            }
        }
    }
    return table[target.length];
};
// m = target.length
// n = array.length
console.log(canConstruct("abcdef",["ab","abc","cd","def","abcd"]))  //true
console.log(canConstruct("skateboard",["bo","rd","ate","t","ska","sk","boar"]));    //false
console.log(canConstruct("enterapotentpot",["a","p","ent","enter","ot","o","t"]));  //true
console.log(canConstruct("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef",[
    "e",
    "ee",
    "eee",
    "eeee",
    "eeeee",
    "eeeeee",
    "eeeeeee"
]));    // false

// brute force
//time O(n ^ m * m)
//space O(m)

// memoized
//time O(n * m * m) = O(n * m ^ 2)
//space O(m)

countConstruct

Write a function countConstruct(target,wordBank) that accepts a target string and an array of strings

The function should return the number of the ways that the target can be constructed by concatenating elements of the wordBank array

you may reuse the elements of wordBank as many times as needed

代码实现

• Memoization

const countConstruct = (target, wordBank, memo = {}) => {
    if (target in memo) return memo[target];
    if (target === '') return 1;
    let totalCount = 0;
    for (let word of wordBank) {
        if (target.indexOf(word) === 0) {
            const numWaysForRest = countConstruct(target.slice(word.length), wordBank, memo);
            totalCount += numWaysForRest;
        }
    }
    memo[target] = totalCount;
    return totalCount;
};
// m = target.length
// n = array.length
console.log(countConstruct("abcdef", ["ab", "abc", "cd", "def", "abcd"]))  //1
console.log(countConstruct("purple", ["purp", "p", "ur", "le", "purpl"]))  //2
console.log(countConstruct("skateboard", ["bo", "rd", "ate", "t", "ska", "sk", "boar"]));    //0
console.log(countConstruct("enterapotentpot", ["a", "p", "ent", "enter", "ot", "o", "t"]));  //4
console.log(countConstruct("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef", [
    "e",
    "ee",
    "eee",
    "eeee",
    "eeeee",
    "eeeeee",
    "eeeeeee"
]));    // 0
// brute force
//time O(n ^ m * m)
//space O(m ^ 2)

// memoized
//time O(n * m * m) = O(n * m ^ 2)
//space O(m ^ 2)

• Tabulation

const countConstruct = (target, wordBank) => {
    const table = Array(target.length + 1).fill(0);
    //初始化制表索引为0的值
    table[0] = 1;

    for (let i = 0;i <= target.length;i++){
        for (let word of wordBank){
            // 检查当前的单词是否与从索引i开始的字符匹配
            if (target.slice(i,i + word.length) === word){
                table[i + word.length] += table[i];
            }
        }
    }
    return table[target.length];
};
// m = target
// n = wordBank.length
console.log(countConstruct("purple", ["purp", "p", "ur", "le", "purpl"]))  //2
console.log(countConstruct("abcdef", ["ab", "abc", "cd", "def", "abcd"]))  //1
console.log(countConstruct("skateboard", ["bo", "rd", "ate", "t", "ska", "sk", "boar"]));    //0
console.log(countConstruct("enterapotentpot", ["a", "p", "ent", "enter", "ot", "o", "t"]));  //4
console.log(countConstruct("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef", [
    "e",
    "ee",
    "eee",
    "eeee",
    "eeeee",
    "eeeeee",
    "eeeeeee"
]));    // 0
// brute force
//time O(n ^ m * m)
//space O(m ^ 2)

// memoized
//time O(n * m * m) = O(n * m ^ 2)
//space O(m)

allConstruct

Write a function allConstruct(target,wordBank) that accepts a target string and an array of strings

The function should return a 2D array containing all of the ways that the target can be constructed by concatenating elements of wordBank array.

Each elements of 2D array should represent one combination that constructs the target

you may reuse the elements of wordBank as many times as needed

代码实现

• Memoization

const allConstruct = (target, wordBank,memo = {}) => {
    if (target in memo) return memo[target];
    if (target === '') return [[]];
    const result = [];
    for (let word of wordBank) {
        if (target.indexOf(word) === 0) {
            const suffix = target.slice(word.length);
            const suffixWays = allConstruct(suffix, wordBank,memo);
            const targetWays = suffixWays.map(way => [word, ...way]);
            result.push(...targetWays);
        }
    }
    memo[target] = result;
    return result;
};


// m = target.length
// n = wordBank.length
console.log(allConstruct("abcdef", ["ab", "abc", "cd", "def", "abcd"]))  //1
// [
//   [ 'abc', 'def' ]
// ]

console.log(allConstruct("purple", ["purp", "p", "ur", "le", "purpl"]))  //2
//    [
//      [ 'purp', 'le' ],
//      [ 'p', 'ur', 'p', 'le' ]
//    ]

console.log(allConstruct("skateboard", ["bo", "rd", "ate", "t", "ska", "sk", "boar"]));    //0
//[]
console.log(allConstruct("enterapotentpot", ["a", "p", "ent", "enter", "ot", "o", "t"]));  //4
//[
//   [ 'enter', 'a', 'p', 'ot', 'ent', 'p', 'ot' ],
//   [
//     'enter', 'a',
//     'p',     'ot',
//     'ent',   'p',
//     'o',     't'
//   ],
//   [
//     'enter', 'a',
//     'p',     'o',
//     't',     'ent',
//     'p',     'ot'
//   ],
//   [
//     'enter', 'a',
//     'p',     'o',
//     't',     'ent',
//     'p',     'o',
//     't'
//   ]
// ]
console.log(allConstruct("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef", [
    "e",
    "ee",
    "eee",
    "eeee",
    "eeeee",
    "eeeeee",
    "eeeeeee"
]));    // []
// time O( n ^ m)
// space O(m)

• Tabulation

const allConstruct = (target, wordBank) => {
    const table = Array(target.length + 1)
        .fill()
        .map(() => []);
    table[0] = [[]];

    for (let i = 0; i <= target.length; i++) {
        for (let word of wordBank) {
            if (target.slice(i, i + word.length) === word) {
                const newCombinations = table[i].map(subArray => [...subArray, word]);
                table[i + word.length].push(...newCombinations);
            }
        }
    }
    return table[target.length];
};


// console.log(allConstruct("abcdef", ["ab", "abc", "cd", "def", "abcd"]))  //1
// console.log(allConstruct("purple", ["purp", "p", "ur", "le", "purpl"]))  //2
// console.log(allConstruct("skateboard", ["bo", "rd", "ate", "t", "ska", "sk", "boar"]));    //0
// console.log(allConstruct("enterapotentpot", ["a", "p", "ent", "enter", "ot", "o", "t"]));  //4
console.log(allConstruct("aaaaaaaaaaaaaaax", [
    "a",
    "aa",
    "aaa",
    "aaaa",
    "aaaaa",
    "aaaaaa",
    "aaaaaaa"
]));    // []


// m : target.length
// n : wordBank.length
// time O( n ^ m)
// space O(m)

总结

• notice any overlapping subproblems（ 注意任何重叠的子问题）
• decide what is the trivially smallest input （决定什么是最小的输入）
• think recursively to use memoization （递归思考虑使用缓存）
• think iteratively to use Tabbulation （迭代考虑使用制表法）
• drew a strategy first （先制定策略）