Two dynamic programming problems

This is the second day of my participation in Gwen Challenge

The basic concept

Dynamic Programming is a mathematical method to solve the optimization of the decision process, and later used in the Programming field. The general idea of dynamic programming is to transform a complex problem into a step-by-step recursion process, from the simple initial state recursion step by step, and finally get the optimal solution of the complex problem. The problem solving process of dynamic programming is divided into two steps:

1. Find the state transition equation
2. Solve the problem from bottom up using state transition equations

Stair climbing problem

Assuming there are n stairs, the only way to climb the stairs is to climb 1 or 2 steps at a time. How many ways can you climb n stairs?

• The last way to climb the stairs:
  • Climb to then-1, climb1order
  • Climb to then-2, climb2order

Derive the equation:

$f(n)=f(n-1) + f(n-2)$

// Time O(N), space O(1)
function climbingWays(n) { // The number of ways to climb n stairs

  // Assume you can only climb one or two steps at a time
  
  if(n < 1) {
    return 0;
  }

  if(n === 1) {
    return 1;
  }

  if(n === 2) {
    return 2;
  }

  // Since only the number of the first two levels is needed to climb the ladder, only two numbers need to be saved
  var a = 1;
  var b = 2;
  var temp = 0;

  for(var i = 3; i <= n; i++) {
    temp = a + b;
    a = b;
    b = temp;
  }

  return temp;

}
Copy the code

Gold mining problem

Suppose there are n gold mines with W workers, and the workers and gold quantity needed by each gold mine are represented by P [] and G [] respectively. Q: The maximum amount of gold mined by all workers.

Because the last gold mine was one of two things: dig or don’t dig.

• There are two cases of maximum substructure:

  • wWorkers dugn-1A gold mine
  • w-p[n-1]Workers dugn-1A gold +g[n-1]

• Edge cases

  • Not enough men to dig a gold mine, or no gold mine
  • Everyone dug the first gold mine

State transition equation

• F (n, w) = 0 (n <= 1, w < p[0]) No gold mine or shortage of manpower
• F (n, w) = g[0] (n == 1, w >= P [0]) Enough men to dig only the first gold mine
• F (n, w) = F (n-1, w) (n > 1, w < p[n-1]) The number of people remaining is less than the number of people needed for this gold mine
• F (n, w) = Max (f (n – 1 w), f (n – 1 w – p/n – 1) + g] [n – 1) (n > 1 w > = p/n – 1) workers is enough

function getMostGold(num, workers, gold, person) {

  var preResult = [];
  var result = [];

  // Determine the boundary condition first
  for(var i = 0; i <= num; i++) {
      if(i < person[0]) {
        preResult[i] = 0;
      } else {
        preResult[i] = gold[0]; }}// Start from the second row and calculate according to the data in the previous row
  // I represents the ith gold mine and j represents the current number of workers
  for(var i = 0; i < num; i++) {

    for(var j = 0; j <= workers; j++) {
      if(j < person[i]) {
        result[j] = preResult[j];
      } else {
        result[j] = Math.max(preResult[j], preResult[j-person[i]]+gold[i])
      }
    }

    // Pass the current value to the next layer and continue traversing
    preResult = result;
  }

  return result[num]; // Finally returns the maximum value
}

Copy the code

When you have a larger number of workers, the number of units you need to create becomes larger, and recursion becomes easier