Print out DP Table to check any errors

DP Problem Properties

Overlapping Subproblems (重复子问题)

  • Occur when a problem can be broken down into smaller subproblems that are solved repeatedly
  • We can store the solutions to the subproblems as we solve them. This allows us to avoid re-solving the subproblems when we encounter them again

Optimal Substructure (最优子结构)

  • Answer to a given problem has to be a Combination of the optimal solution of its smaller problems - solve the smaller problems in the best way possible, we solve the given problem (如果原问题的最优解可以从子问题的最优解构建得来,则它就具有最优子结构)
  • When a problem has optimal substructure, we can use the solutions to the subproblems to construct the solution to the original problem

Knapsack Problem

The solution can be found by combining the optimal solutions to the knapsack problem with smaller weights and values.

Statelessness (无后效性)

  • Solutions to smaller problems are deterministic
  • 给定一个确定的状态, 其未来发展只与该状态有关, 与该状态所经历的过去的所有状态无关
  • 如果未来发展与该状态和该状态的前一个状态相关,我们可以靠矩阵来解。但如果回溯的状态过多,就难了
  • 许多Backtracking problems 都不具有无后效性, 无法使用 Dynamic Programming 快速求解

DP Tools

DP Table

  • Trade space for time
  • Use extra space to hold intermediate results to avoid duplicated computation
  • A mapping between the State and the correspnding solution to each sub-problems at that particular state
  • Can take the form of Array or simply a variable

State Transition Equation (状态转移方程)

  • What is the mathematical operation we need to perform to transit from one state (smaller scope) to the next state (bigger scope), eventually we reach the global state which returns the final answer

0-1 knapsack problem

In 0-1 knapsack problem, the scope is basically the number of the items we can select. The less the items available to be selected the smaller the scope.

The smallest scope is item, in this case, the maximum value we can obtain is always regardless the size of the knapsack bag.

Then we expand the scope from item to item. What is the mathematical operation we need to perform to obtain the new state of the new scope?

The answer is to loop through the knapsack size from to the maximum size. At each size, if the weight of the new item exceeds the knapsack size, we get a bigger knapsack size until we get one that is big enough for the new item. The new state in this case is just the state of the previous smaller scope.

When the knapsack size is big enough, there are 2 choices for us, it is either we put the new item into the bag or we don’t. So how? Remember we want to maximise the value we can have inside the knapsack bag, so we should always make the decision that increments the value in the new state.

Lets abstract the problem:

  • Let be the current knapsack bag size
  • Let be the previous state with , basically the best value we can have with
  • Let be the weight of the new item
  • Let be the value of new item

So now we want to perform state transition which is to obtain the best value with bigger scope at . How should we do that?

The answer is simple, we only put the new item into the knapsack bag if it can generate a bigger value at .

We know the previous state is the best state at that smaller scope. So we can build on top of it! If I put in the new item, the best value it can generate is basically the best value at at the previous state(let this best value be ) + . If we don’t put the new item, the best value is basically .

Thus, we obtain our State Transition Equation. The new state at is Math.max(q + v, p). We put the new item into the bag if , else we don’t.