Front-end job-hopping interview algorithm — Dynamic programming

• The second boundary, F(n*1), is n rows and one column

In this case, any obstacle in the column cannot be passed

Code implementation

export default (arr) => {
  let dp = (m, n) = > {
    // Check whether the starting or target element is 1(obstacle). If the starting or last cell is 1, it means that there is no way to get there.
    // Return 0 directly
    if (arr[m - 1][n - 1= = =1 || arr[0] [0= = =1) {
      return 0
    }
    / / a border
    if (m < 2 || n < 2) {
      // The first boundary is 1 row and n columns
      if (m < 2) {
        return arr[m - 1].includes(1)?0 : 1
      } else {
        // Second boundary n row 1 column
        for (let i = 0; i < m; i++) {
          if (arr[i][0= = =1) {
            return 0}}return 1}}else {
      / / recursion
      return dp(m - 1, n) + dp(m, n - 1)}}return dp(arr.length, arr[0].length)
}Copy the code

Added: Time complexity analysis

Problem analysis

Thank you for your questions in the comments section

First of all, the code above was fine, but the time limit was exceeded on test case 27 on LeetCode

This test case is relatively complex, a 33 by 22 two-dimensional matrix

So why is the time complexity of our method too high when the matrix reaches a certain length?

Let’s review our previous thinking:

• F(10) = F(9) + F(8)             
• F(9) = F(8) + F(7)      

If I factor F of 9, then F of 10 can be written as F of 10

•  F(8) + F(8) + F(7)

F of 8 is equal to F of 7 plus F of 6.

So if WE continue to factor F of 8, F of 10 can be written as F of 10

• F(7) + F(7) +F(7) + F(6) + F(6)

Notice that?

The further down you go, the more repetitions you get, and you might say, well, isn’t that just one more F(n)

But here’s what I have to warn you:

F(n) is not simply a reference to a value, it is a recursive function that repeats F every time we repeat it

So instead of talking about time complexity how do we calculate it

But I can tell you that our previous method was order 2 to the n.

So how to improve?

Put forward the train of thought

Here are two ideas that you can try to write yourself:

1. Cache each calculated value, that is, record F(9),F(8),F(7)… Each time you recurse to the value of the previously calculated data, you directly take the value without having to call the recursive function again.
2. Since only the first two data are relied on each time, only the data of the first two times can be saved through two variables. For example, F(3) only depends on F(1) and F(2), and F(6) only depends on F(5) and F(4).

Code optimization

// Pass in a two-dimensional array
arr => {
    / / the number of rows
    let n = arr.length;
    if(! n){return 0;
    }
    / / the number of columns
    let m = arr[0].length;
    // The starting or ending point is an obstacle
    if(arr[0] [0= = =1 || arr[n - 1][m - 1= = =1) {return 0;
    }
    // Record the number of possible paths to each location
    var rode= [];
    // Iterate over each line
    for(let i = 0; i < n; i++){
        rode[i] = [];    // Iterate over each element in each row
        for(let j = 0; j < m; j++){
            // If a node is an obstacle, the number of paths to that node is 0
            if(arr[i][j] === 1){
                rode[i][j] = 0;
            } else if(i === 0) {// If the first row is passed each node depends on its left node
                rode[i][j] = rode[i][j - 1= = =0 ? 0 : 1;
            } else if(j === 0) {// If the first column is used, each node can pass depending on the node above it
                rode[i][j] = rode[i - 1][j] === 0 ? 0 : 1;
            } else {
                // Otherwise recurse
                rode[i][j] = rode[i - 1][j] + rode[i][j - 1]; }}}return rode[n - 1][m - 1];
}Copy the code

reference

• Programmer Grey – Comics: What is Dynamic Programming?
• The js version of data structure and algorithm
• You can also refer to FE_Yuan’s supplement for this blog: front-end interview algorithm – Dynamic programming

conclusion

Did you notice that when you have the three elements of dynamic programming optimal substructure boundary and state transition formula

Finally, it is not difficult to solve the algorithm problem of dynamic programming. But there are ideas that we need to digest well.

I’m sure you’ll be able to solve these problems in the future.