The Frog’s Story
Frog princess is a far and near famous big beautiful frog 🐸, she wanted to find a clever husband, so set up a challenge, contest: there are continuous board, because the material is different, each board can jump the maximum distance is limited, to recruit the young talent, need to judge, whether can jump to the last board.
Let’s take a look at the input parameters: an array of non-negative integers, with the frog at the first position in the array, and each element in the array representing the maximum length you can jump at that position. The output is simpler: can jump.
Their thinking
According to the general thinking, DFS can certainly be done, but it should not be the most efficient. So, recursively, dynamic programming, and see if there’s any possibility of using a greedy algorithm, and if there’s a greedy algorithm, that might be the simplest path.
Fortunately, this problem can be done either by DFS, dynamic programming or greedy algorithm. I prefer this kind of problem. It is easy to improve by comparing and summarizing different approaches from different ideas. Without further ado, let’s take a look at each one.
Fancy easing the bit in
DFS depth-first algorithm
The most straightforward solution is to perform a RECURSIVE DFS search based on every possible jump distance per board. This algorithm is brainless and has obvious disadvantages: high time complexity and high probability of timeout.
Another Angle: Aim for the last plank. So go ahead and find all the boards that you can jump to, and then target those boards recursively. This algorithm is also mediocre speed, is an optimized version of DFS.
Sure enough, run timeout, frog frog tears.
Dynamic programming
We define an array dp, where dp[I] represents the maximum range that can currently be covered. If the current position is reachable, it is simple to determine whether dp[i-1] is less than I. If it is less than I, it is unreachable. If reachable, update dp[I] = Max(dp[i-1], I +nums[I]).
As can be seen from the execution results in the figure above, the data executed according to dynamic planning is a leap forward compared to DFS, with time consumption reduced by 2/3 and memory consumption reduced by more than 100%. The time complexity should already be optimal. Later, it depends on whether the space can be optimized.
Greedy algorithm
Greedy algorithms, as the name suggests, are greedy enough. If the current board can jump farther than the current board can reach, jump to the current board, otherwise stay on the current board first. Follow this rule and jump to the last board, always standing on the farthest board you can jump. If there is a position in the middle that is unreachable, it is impossible to jump, because on the greedy basis, the current point is already the largest coverage, if this can not jump, other ways can not.
We can see this code, simple and elegant, time-consuming to meet expectations, after writing to their own like 👍, frog prince also have to thank me!
But if you think about it, the code above could have been much cleaner. Because the jump point is not necessary in this case, in other words, we can go from focusing on the jump point to focusing on the distance. The optimized code is as follows, isn’t it clearer?
It’s nothing to make a simple thing complicated. To do complex things more simple, is the key to ability improvement!
The inverse method
In fact, this problem to do here, but also make a feeling. And I thought, is there another way?
Think about it from another perspective, most of the previous forward derivation, but DFS is backward walking, indicating that inverse derivation is feasible, but we dislike DFS efficiency is too low.
For a target position, we move forward to find the nearest board to jump to that position and use that board as our new target. And if you keep going backwards, if you eventually get to the first piece of wood, which is where we started, then you can jump from the beginning to the end.
Notice, let’s think about it a little bit differently than DFS, which is based on the current position, recursively from back to front, all the way to the current board, going through multiple branching paths; And this kind of inverse, which just kind of moves forward, is order n.
Frog frog’s analyse
When viewed from the side of a mountain, all roads lead to Rome. There are so many ways of thinking in a simple springboard movement. Do one thing to the extreme, we will also harvest a lot. To solve algorithm problems, we should not only try beats 100%, but further pursue to thoroughly do all kinds of methods. Each method may have its own advantages and disadvantages, and it is possible to add a restriction condition, so the current optimal solution will become a dead end.
Of course, the most important thing is that this habit trains us to think in a different way. Whether in school or at work, you can give several solutions to a problem, but can’t be the prettiest guy on the street?