Nuggets team number online, help you Offer rimmon! Click to see details
Fibonacci series (Question no. 509)
Take Fibonacci numbers as an example. The concept of a Fibonacci sequence is simple. You start with 0 and 1, and the values of the next two numbers are the sum of the first two:
0 1 1 2 3 5 8 13...Copy the codelink
Leetcode-cn.com/problems/fi…
Basic solution
OK, let’s start with the basic concepts. Let’s start with the simplest recursive method that comes to mind right from the start:
function fib(n) {
return n <= 1 ? n : fib(n - 1) + fib(n - 2)
}
Copy the codeThe method of this piece is relatively simple. First, judge whether it is 0 or 1 (the case that n is less than 0 is not considered here, and the same will not be repeated hereafter). If yes, return n, otherwise return the sum of the first two digits.
This method looks very simple, but if you simply print it out you will see that it is executed a lot, close to 2 to the n. Here is an example:
var count = 0
function fib(n) {
count++
return n <= 1 ? n : fib(n - 1) + fib(n - 2)
}
fib(5)
console.log(count) // 15
count = 0
fib(10)
console.log(count) // 177
Copy the codeObviously, we’ve just counted to 10 and we’ve already executed 177 times, which is pretty inefficient, but what if we remember the previous value every time, and the reason why we’re going through it so many times is because we’re factoring n every time, is it okay to remember n the first time we see n?
Advanced solutions
Yes, this method does reduce a lot of work:
var count = 0 function fib2(n, meno = []) { count++ if (n === 0 || n === 1) { return n } else if (! meno[n]) { meno[n] = fib2(n - 1, meno) + fib2(n - 2, meno) return meno[n] } else { return meno[n] } } fib2(5) console.log(count) // 9 count = 0 fib2(10) console.log(count) / / 19Copy the codeBecause I remember the value of n every time I recurse, MOST of the recursion times are reduced, if there is a direct value.
Is there a better way? This is also O(2n) time, because each number has to be traversed twice.
Dynamic programming
Yes, that’s dynamic programming. The essence of dynamic programming is recursion + memory. Without further comment, just look at the code:
var count = 0
function fib3(n) {
var arr = [0, 1]
for (let i = 2; i <= n ; i++) {
count++
arr[i] = arr[i - 1] + arr[i - 2]
}
return arr[n]
}
fib3(5)
console.log(count) // 4
count = 0
fib3(10)
console.log(count) // 9
Copy the codeAs you can see, the number of loops in the above code is very small, so it can be regarded as O(n) time complexity, and this is dynamic programming, so you only need to take the first two values each time without having to execute the function again, and you can get the final result if you just take arr[n].
The optimal path
This is also a very common problem in dynamic programming, specifically in Leetcode 62 and 63, so let’s start with 62, and it looks like this:
Simple version (Question No. 62)
Link: leetcode-cn.com/problems/un…
A robot is located in the upper left corner of an m x N grid (the starting point is marked “Start” in the image below).
The robot can only move one step down or to the right at a time. The robot tries to reach the lower right corner of the grid (marked “Finish” in the image below).
How many different paths are there?
Input: m = 3, n = 7 Output: 28Copy the codeIt’s such a simple problem, the normal idea is to go from the first cell, one to the right and one to the bottom, and then go through the next cell and one to the right, so a little bit down, and finally you can get the result. But in terms of actual code, it’s hard to write code this way of thinking about it, so let’s do it the other way around, let’s go from the bottom right corner to the top left corner, and every time you go to the bottom right corner, you can only go to the right and you can only go down, so you just add the bottom and the right corner.
So the first thing you would do is you would recurse, you would take the coordinates of the current cell, and you would do x minus 1 and y minus 1, and then you would do the same thing with x minus 1, and you would get x minus 1 and y minus 1, and so on.
It does work, and the way you think about it is a bit like the Fibonacci base solution above. But the problem is the same, and this one is more complicated, and performance is going to be a big problem, and somebody on LeetCode has written a recursive solution, and the result is timeout.
Since the coordinates of each lattice are unique, we cannot use the advanced solution of Fibonacci sequence, and we cannot use the method of storing data to reduce the recursion times, so we directly use the method of dynamic programming:
var uniquePaths = function(m, n) {
var board = []
for (let i = 0; i < m; i++) {
board[i] = new Array(n)
}
for (let i = m - 1; i > -1; i--) {
for (let j = n - 1; j > -1; j--){
if (i === m - 1 && j === n - 1) {
board[i][j] = 1
} else {
board[i][j] = (i + 1 < m ? board[i + 1][j] : 0) + (j + 1 < n ? board[i][j + 1] : 0)
}
}
}
return board[0][0]
};
Copy the codeThe overall logic is nothing to say. Use the board to store data, starting from the end, and recording the possible paths from the current cell to the beginning. If the next cell or the right cell is out of bounds, it is treated as 0. The result is the value starting with board.
The 👆 code has some shorthand for determining boundary conditions, but you can do it otherwise, and it’s a little easier to understand and look more comfortable if you take the ternary out.
Upgraded version (Question 63)
Link: leetcode-cn.com/problems/un…
What if I add an unwalkable place to the path, for example, given a two-dimensional array:
[[0,0,0], [0,1,0], [0,0,0]]Copy the code0 is where you can go, 1 is where you can’t go, in this case finding the possible path from [0][0] to [2][2].
You can easily get the answer by looking at the simple version above, and the code looks similar:
var uniquePathsWithObstacles = function(obstacleGrid) { var board = [] row = obstacleGrid.length - 1 col = obstacleGrid[0].length - 1 for (let i = row; i > -1; i--){ board[i] = new Array(col) for (let j = col; j > -1; j--) { if (i === row && j === col) { if (obstacleGrid[i][j] === 1) return 0 board[i][j] = 1 } else { var res = 0 if (obstacleGrid[i][j] ! == 1) { res = (i + 1 > row ? 0 : board[i + 1][j]) + (j + 1 > col ? 0 : board[i][j + 1]) } board[i][j] = res } } } return board[0][0] };Copy the codeThe only difference is that we added a criterion for 1, nothing else, but as soon as we committed the code, we found that the performance of this writing was in the bottom 40% of all the answers, which is obviously not what we wanted, so what better way to do it?
A better answer (elegant)
In the code for 👆, the criteria in the two-level loop are a little too complicated. Is there any way to simplify them? Apparently there is.
The first row and the first column of the board can be calculated first, so that there is no need to make complex conditions in the double-layer loop, and this can optimize the conditions of the loop, remove the boundary value judgment.
First look at the code:
const uniquePathsWithObstacles1 = (obstacleGrid) => { if (obstacleGrid[0][0] == 1) return 0; Const m = obstaclegrid.length; const n = obstacleGrid[0].length; Const dp = new Array(m); for (let i = 0; i < m; i++) dp[i] = new Array(n); // base case dp[0][0] = 1; For (let I = 1; i < m; I++) {/ / the rest of the first column case dp [I] [0] = (obstacleGrid [I] [0] = = 1 | | dp [I - 1] [0] = = 0)? 0:1; } for (let i = 1; i < n; I++) {/ / the first line of the rest of the case dp [0] [I] = (obstacleGrid [0] [I] = = 1 | | dp [0] [I - 1] = = 0)? 0:1; } console.log(dp) // iterates for (let I = 1; i < m; i++) { for (let j = 1; j < n; j++) { dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i - 1][j] + dp[i][j - 1]; } } return dp[m - 1][n - 1]; // The number of paths to (m-1,n-1)};Copy the codeSo dp is the board, which is dynamic Program.
First get the first row and first column of dp, and then get the first row and first column of DP:
[[1,1,1], [1,,]]Copy the codeThen the loop m and n can start at 1, and then j-1 and i-1 won’t go beyond the boundary, so it saves a lot of judgment.
A simple judgment is required inside a double cycle.
But if you run it, it doesn’t increase performance very much, so what else can you do?
Better answer (dimension reduction)
This is not very easy to understand, indeed, I also read several times to understand the true meaning of this answer, this question is estimated to say not understand, start to write, write out the result after each cycle I.
var uniquePathsWithObstacles = function(obstacleGrid) { var n = obstacleGrid.length; var m = obstacleGrid[0].length; var result = Array(m).fill(0); for(var i = 0; i < n; i++){ for(var j = 0; j < m; j++){ if(i == 0 && j == 0){ result[j] = 1; } if(obstacleGrid[i][j] == 1){ result[j] = 0; }else if(j > 0){ result[j] += result[j-1]; } } } return result[m-1]; };Copy the codeIt’s hard to understand, but I have to say that the performance of this method is a lot stronger, jumping directly into the top 90%.
summary
The basic introduction of dynamic programming is paste, or as the beginning said, recursion (dynamic programming) = recursion + memory.
You can also think of it as recursion or memorization and then dynamic programming, but it’s not as hard as you think.
PS: To view past articles and titles, click on the link below:
Here’s 👇 by date
Front Brush path – Directory (Date classification)
After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇
Front brush problem path – Catalogue (Question type classification)
Those who are interested can also check out my personal homepage 👇
Here is RZ