Jeremy

Weighted Interval Scheduling 加权区间调度

Definition of Dynamic programming

  • A technique for solving optimisation problems.

  • The paradigm of dynamic programming:

  • Given a problem P, define a sequence of subproblems, with the following properties: (定义一系列的子问题)

    • The subproblems are ordered from the smallest to the largest. 从小问题到大问题

    • The largest problem is our original problem P. 最大的问题是 P

    • The optimal solution of a subproblem can be constructed from the optimal solutions of sub-sub-problems. (Optimal Substructure). 子问题的最优解可以被更小的子子问题最优解解决

  • Solve the subproblems from the smallest to the largest. When you solve a subproblem, store the solution (e.g., in an array) and use it to solve the larger subproblems.

Definition of Weighted Interval Scheduling

  • A set of requests {1, 2, … , n}.

    • Request i has a starting time s(i), a finishing time f(i), and a value v(i).

    • Alternative view: Every request is an interval [s(i), f(i)] associated with a value v(i).

  • Two requests i and j are compatible if their respective intervals do not overlap.

  • Goal: Output a schedule which maximises the total value of compatible intervals.

Subset Sum

The subset sum problem

  • We are given a set of n items {1, 2, … , n}.

  • Each item i has a non-negative weight wi.

  • We are given a bound W.

  • Goal: Select a subset S of the items such that sum_i wi <= W and sum_i 𝑤i is maximised.

Dynamic Programming

  • We need to identify the appropriate subproblems to use in order to solve the main problem.

  • Recall the weighted interval scheduling problem. Similar approach.

  • Let OPT(i) be the optimal solution to the subset sum problem, using a subset of {1, 2, … , i}.

    • Let Oi be its value and hence O is On.

  • Should item n be in the optimal solution O or not?

    • If no, then OPT(n-1) = OPT(n)

    • If yes, ?

  • Subproblems

    • Using this notation, what are we looking for?

    • OPT(n,W)

    • Should item n be in the optimal solution O or not?

    • If no, then OPT(n,W) = OPT(n-1,W).

    • If yes, then OPT(n,W) = wn + OPT(n-1,W-wn).

  • Example
function subsetSum(arr, maxSum) {
  let res = [[]];
  for (let i = 0; i <= maxSum; i++) {
    res[0].push(0);
  }
  for (let i = 1; i <= arr.length; i++) {
    res[i] = [0];
    for (let j = 0; j <= maxSum; j++) {
      if (arr[i - 1] > j) {
        res[i][j] = res[i - 1][j];
      } else {
        res[i][j] = Math.max(
          res[i - 1][j],
          arr[i - 1] + res[i - 1][j - arr[i - 1]]
        );
      }
    }
  }
  console.log(res);
}

/**
 * 
 * 
3: [0, 0, 2, 3, 4, 5, 5]
2: [0, 0, 2, 2, 4, 4, 4]
1: [0, 0, 2, 2, 2, 2, 2]
0: [0, 0, 0, 0, 0, 0, 0]
 */

  • Running Time O(nW)

Knapsack

动态规划三大步骤

  1. 定义数组元素的含义，假设定义一个一维数组，那么需要明白 dp[i]代表什么意思
  2. 找出数组元素之间的关系式，类似于数学归纳法，当计算 dp[n]时，可以从 dp[n - 2],dp[n - 1]中推导出 dp[n]的值
  3. 找出初始值，例如 dp[4] = dp[3] + dp[2]，而 dp[3] = dp[2] + dp[1]。dp[2]和 dp[1]不能再分，这就是初始值

案例

青蛙跳台阶(简单)

描述：一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

1.找出数组含义

dp[n]的含义是：青蛙跳上一个 n 级的台阶总共有多少种跳法

2.找出数组之间的关系式

由题可知，可以选择跳一级，也可以选择跳二级。所以可以得到 dp[n] = dp[n - 1] + dp[n - 2]

3.找出初始值

n 不能为负数，由题可知，dp[1] = 1，dp[0] = 0，dp[2] = 2。

写出算法

  function getMethods(num) {
    let dp = [0, 1, 2];
    if (num <= dp.length) return dp[num]
    for(let i = 3, i < num.length; i++) {
      dp.push(dp[i - 1] + dp[i - 2])
    }

    return dp[num.length - 1]
  }

案例 2：找出到达终点的所有路径

描述：一个机器人位于一个 m x n  网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

dp 定义

表示有多少种方法可以走到 i,j 这个格子

找出数组之间的关系式

dp[i][j] = dp[m][n - 1] + dp[m - 1][n]

定义初始值

dp[0][0] = 1 dp[1][0] = 1 dp[0][1] = 1

写出算法

var dp = [[1, 1], [1]];
for (let i = 0; i < m; i++) {
  for (let j = 0; j < n; j++) {
    if (!dp[i]) dp[i] = [];
    if (!dp[i][j])
      dp[i][j] = (dp[i][j - 1] || 0) + (i - 1 >= 0 ? dp[i - 1][j] : 0);
  }
}
return dp[m - 1][n - 1];

案例 3: 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。

dp 定义

dp[i][j] 表示路径数字总和的最小值

找出数组之间的关系式

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

找出默认值

dp[0][0] = grid[0][0]

题解

// dp[i][j] 表示路径数字总和的最小值
// dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
// 网格内有默认值
let m = grid.length;
let n = grid[0].length;
let dp = [[grid[0][0]]];
for (let i = 0; i < m; i++) {
  if (!dp[i]) dp[i] = [];
  for (let j = 0; j < n; j++) {
    if (i === 0 && j === 0) continue;
    if (j === 0) {
      dp[i][j] = dp[i - 1][j] + grid[i][j];
    } else if (i === 0) {
      dp[i][j] = dp[i][j - 1] + grid[i][j];
    } else {
      dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
    }
  }
}

return dp[m - 1][n - 1];