Shulou(Shulou.com)06/03 Report--

This article introduces the relevant knowledge of "what is the evolution of Fibonacci series". In the operation of actual cases, many people will encounter such a dilemma. Next, let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

1: violent recursion

Often we are faced with a problem, even if we clearly know that it is a "no aftereffect" problem, it can be solved through "dynamic planning". We still find it difficult to get started.

At this point, my suggestion is to write a version of "violent recursion" first.

Or with the LeetCode 62 just mentioned. For example, Unique Paths:

Class Solution {public int uniquePaths (int m, int n) {return recursive (m, n, 0,0);} private int recursive (int m, int n, int I, int j) {if (I = = m-1 | j = = n-1) return 1; return recursive (m, n, I + 1, j) + recursive (m, n, I, j + 1);}}

When I don't know how to use dynamic programming to solve the problem, I design a recursive function recursive ().

The function passes in the matrix information and the current position of the robot, and returns how many paths there are from the position of the robot to the lower right corner in this matrix.

With this recursive function, the problem is actually solving recursive (m, n, 0): the number of paths from (0, 0) to the lower right corner.

Next, implement this function:

Base case: because the title makes it clear that the robot can only go down or right, the base case of the recursive method can be determined when it is already in the last row or column of the matrix, that is, there is only one way to go.

The rest: the robot can go either to the right or down, so for a certain position, the number of paths to the lower right corner is equal to the number of paths to the lower right corner in its right position + the number of paths below it to the lower right corner. That is, recursive (m, n, I + 1, j) + recursive (m, n, I, j + 1), these two positions can be solved by recursive functions.

In fact, we have solved this problem by now.

But there is also a serious performance problem with this approach.

2: memory search

If we submit the above code to LeetCode, we will get the result of timeout.

It can be seen that the solution of "violent recursion" is "very slow".

We know that the essence of all recursive functions is "stack" and "bounce stack".

Since this process is slow, can we solve the timeout problem by changing the recursive version of the brute force solution to a non-recursive brute force solution?

The answer is no, because the cause of timeout is not the cost of using "recursive" means.

But in the calculation process, we have carried out a number of repeated calculations.

Let's try to unfold the recursive process and take a look at the following steps:

It is not difficult to find that there are a lot of repeated calculations in the process of recursive expansion.

With the development of our whole recursive process, the number of repeated calculations will increase in multiples.

This is the reason why the "violent recursion" solution is "slow".

Since the timeout is caused by double calculation, we will naturally think of a solution to "cache" the calculation results:

Class Solution {private int [] [] cache; public int uniquePaths (int m, int n) {cache = new int [m] [n]; for (int I = 0; I

< m; i++) { int[] ints = new int[n]; Arrays.fill(ints, -1); cache[i] = ints; } return recursive(m, n, 0, 0); } private int recursive(int m, int n, int i, int j) { if (i == m - 1 || j == n - 1) return 1; if (cache[i][j] == -1) { if (cache[i + 1][j] == -1) { cache[i + 1][j] = recursive(m, n, i + 1, j); } if (cache[i][j + 1] == -1) { cache[i][j + 1] = recursive(m, n, i, j + 1); } cache[i][j] = cache[i + 1][j] + cache[i][j + 1]; } return cache[i][j]; }} 对「暴力递归」过程中的中间结果进行缓存，确保相同的情况只会被计算一次的做法，称为「记忆化搜索」。 做了这样的改进之后，提交 LeetCode 已经能 AC 并得到一个不错的评级了。 我们再细想一下就会发现，其实整个求解过程，对于每个情况（每个点）的访问次数并没有发生改变。 只是从「以前的每次访问都进行求解」改进为「只有第一次访问才真正求解」。 事实上，我们通过查看 recursive() 方法就可以发现： 当我们求解某一个点 (i, j) 的答案时，其实是依赖于 (i, j + 1) 和 (i + 1, j) 。 也就是每求解一个点的答案，都需要访问两个点的结果。 这种情况是由于我们采用的是"自顶向下"的解决思路所导致的。 我们无法直观确定哪个点的结果会在什么时候被访问，被访问多少次。 所以我们不得不使用一个与矩阵相同大小的数组，将所有中间结果"缓存"起来。 换句话说，「记忆化搜索」解决的是重复计算的问题，并没有解决结果访问时机和访问次数的不确定问题。 2.1：次优解版本的「记忆化搜索」 关于「记忆化搜索」最后再说一下。 网上有不少博客和资料在编写「记忆化搜索」解决方案时，会编写类似如下的代码： class Solution { private int[][] cache; public int uniquePaths(int m, int n) { cache = new int[m][n]; for (int i = 0; i < m; i++) { int[] ints = new int[n]; Arrays.fill(ints, -1); cache[i] = ints; } return recursive(m, n, 0, 0); } private int recursive(int m, int n, int i, int j) { if (i == m - 1 || j == n - 1) return 1; if (cache[i][j] == -1) { cache[i][j] = recursive(m, n, i + 1, j) + recursive(m, n, i, j + 1); } return cache[i][j]; }} 可以和我上面提供的解决方案作对比。主要区别在于 if (cache[i][j] == -1) 的判断里面。 在我提供解决方案中，会在计算 cache[i][j] 时，尝试从"缓存"中读取 cache[i + 1][j] 和 cache[i][j + 1]，确保每次调用 recursive() 都是必须的，不重复的。 网上大多数的解决方案只会在外层读取"缓存"，在真正计算 cache[i][j] 的时候并不采取先检查再调用的方式，直接调用 recursive() 计算子问题 。 虽然两者相比与直接的「暴力递归」都大大减少了计算次数（recursive() 的访问次数），但后者的计算次数显然要比前者高上不少。 你可能会觉得反正都是"自顶向下"，两者应该没有区别吧？ 为此我提供了以下实验代码来比较它们对 recursive() 的调用次数： class Solution { public static void main(String[] args) { Solution solution = new Solution(); solution.uniquePaths(15, 15); } private int[][] cache; private long count; // 统计 递归函数 的调用次数 public int uniquePaths(int m, int n) { cache = new int[m][n]; for (int i = 0; i < m; i++) { int[] ints = new int[n]; Arrays.fill(ints, -1); cache[i] = ints; } // int result = recursive(m, n, 0, 0); // count = 80233199 // int result = cacheRecursive(m, n, 0, 0); // count = 393 int result = fullCacheRecursive(m, n, 0, 0); // count = 224 System.out.println(count); return result; } // 完全缓存 private int fullCacheRecursive(int m, int n, int i, int j) { count++; if (i == m - 1 || j == n - 1) return 1; if (cache[i][j] == -1) { if (cache[i + 1][j] == -1) { cache[i + 1][j] = fullCacheRecursive(m, n, i + 1, j); } if (cache[i][j + 1] == -1) { cache[i][j + 1] = fullCacheRecursive(m, n, i, j + 1); } cache[i][j] = cache[i + 1][j] + cache[i][j + 1]; } return cache[i][j]; } // 只有外层缓存 private int cacheRecursive(int m, int n, int i, int j) { count++; if (i == m - 1 || j == n - 1) return 1; if (cache[i][j] == -1) { cache[i][j] = cacheRecursive(m, n, i + 1, j) + cacheRecursive(m, n, i, j + 1); } return cache[i][j]; } // 不使用缓存 private int recursive(int m, int n, int i, int j) { count++; if (i == m - 1 || j == n - 1) return 1; return recursive(m, n, i + 1, j) + recursive(m, n, i, j + 1); }} 因为我们使用 cache 数组的目的是减少 recursive() 函数的调用。 只有确保在每次调用 recursive() 之前先去 cache 数组检查，我们才可以将对 recursive() 函数的调用次数减到最少。 在数据为 15 的样本下，这是 O(393n) 和 O(224n) 的区别，但对于一些卡常数特别严重的 OJ，尤其重要。 所以我建议你在「记忆化搜索」的解决方案时，采取与我一样的策略： 确保在每次访问递归函数时先去"缓存"检查。尽管这有点"不美观"，但它能发挥「记忆化搜索」的最大作用。 3：从「自顶向下」到「自底向上」 你可能会想，为什么我们需要改进「记忆化搜索」，为什么需要明确中间结果的访问时机和访问次数？ 因为一旦我们能明确中间结果的访问时机和访问次数，将为我们的算法带来巨大的提升空间。 前面说到，因为我们无法确定中间结果的访问时机和访问次数，所以我们不得不"缓存"全部中间结果。 但如果我们能明确中间结果的访问时机和访问次数，至少我们可以大大降低算法的空间复杂度。 这就涉及解决思路的转换：从「自顶向下」到「自底向上」 。 如何实现从「自顶向下」到「自底向上」的转变，还是通过具体的例子来理解。 这是 LeetCode 509. Fibonacci Number，著名的"斐波那契数列"问题。 如果不了解什么是"斐波那契数列"，可以查看对应的 维基百科。 由于斐波那契公式为：

Naturally suitable for recursion:

Public class Solution {private int [] cache; public int fib (int n) {cache = new int [n + 1]; return recursive (n);} private int recursive (int n) {if (n)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.