Problem 1: Fibonacci sequence

The Fibonacci sequence starts with 1, 1, 2, 3, 5, 8, 13, 21, 34… Each of the following terms is the sum of the first two terms. In fact, Fibonacci mathematically has its own strict recursive definition.

f0 = 1 f1 = 1 f(n) = f(n-1) + f(n-2)

Method one: recursive solution

function fib(n) {
  if (n == 1 || n == 2) {
    return 1;
  }
  return fib(n - 1) + fib(n - 2);
}

console.log(fib(10))
Copy the code

This is easy to think of, as long as we implement mathematical recursion in code.

A problem

Run the following result:

function fib(n) {
  if (n == 1 || n == 2) {
    return 1;
  }
  return fib(n - 1) + fib(n - 2);
}
console.time()
console.log(fib(10)) // 55 Time: 9.102ms
console.timeEnd()

console.time()
console.log(fib(44)) // 701408733 Time: 6.494s
console.timeEnd()
Copy the code

We find that it takes 6.5 seconds to calculate the 44th term, so if we calculate the 100th term, we can’t calculate the destruction of the universe. What should we do?

Where does it affect the time consuming

​

So by tree decomposition, we found out that we did double counting, we computed fib of 3 twice, fib of 2 three times.Oh oh, I see. It’s time consuming caused by double calculation. We know what caused the problem, so we can optimize it. ​

Method 2: Increase the cache

/ / performance is poor
function fib1(n) {
    const cache = [];
    var res = helper(cache, n);
    return res;
}

function helper(cache, n) {
    if (n == 1 || n == 2) {
        cache[n] = 1;
        return 1;
    }
    if (cache[n]) return cache[n];
    var res = helper(cache, n - 1) + helper(cache, n - 2);
    cache[n] = res;
    return res;
}
Copy the code

We use cache arrays for caching to reduce double-counting.

Running results:

console.time()
console.log(fib1(10)) // 55 Time: 9.102ms
console.timeEnd()

console.time()
console.log(fib1(44)) // 701408733 Time: 9.599ms
console.timeEnd()
Copy the code

Time complexity is down. Perfect.

Continue to test

console.time()
console.log(fib1(144)) //5.5556540422429276e+29 time: 9.229ms
console.timeEnd()


console.time()
console.log(fib1(14400))  / /??????
console.timeEnd()
Copy the code

When the 14,400th term is calculated, the following happens What’s going on here? I didn’t write an endless loop, it actually appearedDead loop error ？？？？ Analyze the reasons,The discovery is because JS opens up the function is limited, does not allow to create too many functions, the function reaches a certain magnitude, will consider isInfinite loop. ​

I have no choice but to continue to optimize

Method 3: Use loops instead of recursion

function fib2(n){
  let dp = []
  dp[1] = 1;
  dp[2] = 2;
  for(var i=3; i<=n; i++){ dp[i] = dp[i-1] + dp[i-2]}return dp[n];
}
Copy the code

With the code above, we can easily count the millionth column.

Conclusion; When doing large calculations, you need to abandon recursion and use a for or while loop, otherwise you will be warned of an infinite loop.

​

Problem two: change problem

For a real life change problem, suppose you have an unlimited number of 20,10,5,1 coins. Find the change solution by using the smallest number of coins. For such problems, the greedy algorithm takes the approach of always picking the maximum number of coins available for change. For example, if you have a change of 25, use 20+5 instead of 10+10+5.

This idea is also quite good: we take the whole money to face value, from the largest start to find, if not enough to find, find the next face value, this idea can find a solution, this kind of thinking in the algorithm called greedy algorithm.

class Change1 {
  constructor(changeType) {
    // In reverse order, the larger number comes first
    this.changeType = changeType.sort((r1, r2) = > r2 - r1);
    this.cache = {};
  }
  mkChange(amount) {
    const arr = [];

    for (let i = 0; i < this.changeType.length; i++) {
      let tem = this.changeType[i];
      while (amount - tem >= 0) { arr.push(tem); amount -= tem; }}returnarr; }}var c = new Change1([20.10.5.1])

console.log(c.mkChange(126))

/ / the answer
[
  20.20.20.20.20.20.5.1
]

Copy the code

Well, we came up with a result. We took five twenties, one five, one one one. Done.

A problem

When we change face value and change, the result may not be correct. For example, if the denominations in which change is provided are 11,5,1, change 15.

var c = new Change1([11.5.1])
console.log(c.mkChange(15))11.1.1.1.1 ] 
Copy the code

But from our normal analysis, we know that three fives is the right answer. So in this case, greedy algorithms can’t find an optimal solution.

If we want to find the optimal solution, we need to use dynamic programming.

Analysis of the

0: since 0 doesn’t require coins, the result is 0: f(0) = 0; 1 yuan: Since there are 1 yuan coins available, we can use a 1 yuan coin first, and then raise 0 yuan, and the value of f(0) is already calculated, so: F (1) = 1 + F (0) = 1 + 0 = 1.

2 yuan: In the four denominations of coins, only 1 yuan is smaller than 2 yuan, so we can only use a 1 yuan coin first, and then raise 1 yuan, and we have calculated the value of f(1), so: F (2) = 1 + F (1) = 1 + 1 = 2, where the 1 in F (2) = 1 + F (1) represents a 1 yuan coin;

F (3) = 1 + F (2) = 1 + 2 = 3;

F (4) = 1 + F (3) = 1 + 3 = 4;

$5: There’s more than one option, because there’s a $5 coin. Plan 1: Use a coin of 5 yuan, and raise enough money to 0 yuan, then: F (5) = 1 + F (0) = 1 + 0 = 1, here f(5) = 1 + F (0) 1 means use a coin of 5 yuan; F (5) = 1 + F (4) = 1 + 4 = 5. F (5) = min{1 + f(0),1 + f(4)} = 1;

Make up 6 dollars: there are two options at this time, plan 1: first use a 1 dollar, and then make up enough 5 dollars, that is: F (6) = 1 + F (5) = 1 + 1 = 2; F (6) = 1 + F (1) = 1 + 1 = 2. Combining the two schemes, there are: f(6) = min{1 + f(5), 1 + f(1)} = 2;

… (omitted)

As can be seen from the above analysis process, the minimum value of each of the following options should be considered in order to raise enough I dollars: 1 + f(i-value [j]), where value[j] represents the JTH value (j starts from 0, 0 <= j < 4) and value[j] <= I

f(i) = 0, i = 0 ​

f(i) = 1, i = 1 ​

F (I) = min {1 + f (I – value [j])}, I > 1, the value [j] < = I

code

// Dynamic programming
class Change {
  constructor(changeType) {
    this.changeType = changeType;
    this.cache = {};
    this.typeCount = {};
    this.fn = {};
  }
  // Find the optimal solution to the amount dollar and cache it
  mkChange(amount) {
    let min = []; // Final solution
    if(! amount) {return [];
    }
    if (this.cache[amount]) {
      return JSON.parse(this.cache[amount]);
    }
    for (let i = 0; i < this.changeType.length; i++) {
      // Try one first
      const hasAmount = amount - this.changeType[i];
      let newMin; // Temporary solution
      if (hasAmount >= 0) {
        // Keep looking for money
        newMin = this.mkChange(hasAmount);
      }
      if (hasAmount >= 0) {
        if (newMin.length < min.length) {
          min = [this.changeType[i]].concat(newMin);
        }
        if (min.length === 0) {
          // If the optimal solution does not exist, then it is inherently optimal
          min = [this.changeType[i]].concat(newMin); }}}this.cache[amount] = JSON.stringify(min);
    return min;
  }
  mkChangefn(amount, limit = 100) {
    let calc = 0;
    while (amount > calc) {
      calc += 1;
      this.mkChange(calc);
    }
    return this.mkChange(amount).join(","); }}var c = new Change([11.5.1])
console.log(c.mkChangefn(15)) / / 5,5,5
Copy the code