Every dynamic programming algorithm starts with a grid. It entails solving subproblems and builds up to solving the big problem. Let’s break down a problem and solve it in pieces using dynamic programming with JavaScript.

 

/** * 给一个浮点数序列，取最大乘积连续子串的值，例如 -2.5，4，0，3，0.5，8，-1，则取出的最大乘积连续子串为3，0.5，8。也就是说，上述数组中，3 0.5 8这3个数的乘积30.58=12是最大的，而且是连续的 * @param {*} a  */function MaxProductSubstring (a) {    let maxEnd = a[0]    let maxRes = a[0]    for (let i = 1; i < a.length; i++) {        maxEnd = Math.max(maxEnd * a[i], a[i])        maxRes = Math.max(maxRes, maxEnd)    }    return maxRes}

 

 

Example two:

const rope = { value: 1500, weight: 1 };const food = { value: 2000, weight: 3 };const tent = { value: 3000, weight: 4 };const iphone = { value: 2000, weight: 1 };const constraint = [1, 2, 3, 4];const items = [rope, tent, food, iphone];/** * Dynamic progamming * *       |  1   | 2   | 3    | 4 * rope  | 1500 |1500 | 1500 | 1500 * ------------------------------- * tent  | 1500 |1500 | 1500 | 3000 * ------------------------------- * food  | 1500 |1500 | 2000 | 3500 * ------------------------------- * iphone| 2000 |3500 | 3500 | 4000 * ------------------------------- * * row(i) = weight > constraint(j) ? row(i-1) : 0 * row(i) = weight = constraint(j) ? ( value > row(i-1) ? value : row(i-1) ) : value * row(i) = weight < constraint(j) ? value + row[i-1][diff] > row[i-1] ? value + row[i-1][diff] : row[i-1] *  where diff = constraint(j) - weight */function getMaxValue(items, constraint) {  let grid = [...Array(items.length)].map(e => Array(constraint.length));  function helper(items, constraint, grid) {    for (let row in items) {      const { value, weight } = items[row];      for (let col in constraint) {        // take care the first row        if (grid[row - 1] === undefined) {          grid[row][col] = weight <= constraint[col] ? value : 0;          continue;        }        // if weight is larger than constraint, take previous row value        const prevRowSameCol = grid[row - 1][col];        if (weight > constraint[col]) {          grid[row][col] = prevRowSameCol;          continue;        }        // if weight equals constraint, Max { value , row(i-1)}        if (weight === constraint[col]) {          grid[row][col] = Math.max(value, prevRowSameCol);          continue;        }        // if weight samller than constraint, Max { value + row[i-1][diff] , row(i-1)}        if (weight < constraint[col]) {          const diff = constraint[col] - weight - 1;          console.log(diff, grid[row - 1][diff]);          grid[row][col] = Math.max(            value + grid[row - 1][diff],            prevRowSameCol          );        }      }    }    return grid;  }  return helper(items, constraint, grid);}const res = getMaxValue(items, constraint);document.body.append(JSON.stringify(res, null, 2));/**  * [  *  [ 1500, 1500, 1500, 1500 ],  *  [ 1500, 1500, 1500, 3000 ],  *  [ 1500, 1500, 2000, 3500 ],  *  [ 2000, 3500, 3500, 4000 ]  * ] * */