How to avoid stack problems（记忆化出场）

1- If must do it in recursion, then avoid any unnecessary local data. Move to global as possible
2- Move to iterative procedure
3- Implement your own stack calls!

  1. // Fibonacci Series: Fib(n) = fib(n-1) + fib(n-2).    Fib(0) = fib(1) = 1
  2. int fib(int n)
  3. {
  4.     if(n <= 1)
  5.         return 1;
  7.     return fib(n-2) + fib(n-1);
  8. }
  10. // what is search space? n
  11. // what is number of recursive calls? We are branching every time to 2 levels that differs in 1
  12. //                                        fib(5)
  13. //                            fib(4)                                            fib(3)
  14. //                fib(3)                    fib(2)                        fib(2)            fib(1)
  15. //        fib(2)            fib(1)    fib(1)            fib(0)        fib(1)            fib(0)
  16. //    fib(1)    fib(1)
  17. //
  18. // We almost have 2^N calls
  20. // Wait, a space of N, is called 2^N times!
  21. // A fib of 50 do around ~1125899906842624 call!!!!!!
  22. //
  23. // Then, we must call a state more than once? and it too call other states, that already called!
  24. //
  25. // Check tree above, fib(3) called twice. Fib(2) called three times!
  26. //
  27. // Let's SAVE the answer, and let space of N is called 2N times!
  30. int savedAnswers[MAX];        /// Initialized to -1, means no answer
  31. int fibSave(int n)
  32. {
  33.     if(n <= 1)
  34.         return 1;
  36.     if(savedAnswers[n] != -1)
  37.         return savedAnswers[n];
  39.     return savedAnswers[n] = fib(n-2) + fib(n-1);
  40. }
  42. //                                                    fib(5)=8
  43. //                                    fib(4)=5                            fib(3)=3
  44. //                        fib(3)=3                    fib(2)=2
  45. //            fib(2)=2                fib(1)=1
  46. //    fib(1)=1        fib(1)=1

memoization记忆化

记忆化搜索，是在学习动态规划的时候，用到的。用记忆化搜索的方式，实现dp。在这个章节，练习题目时，也请感受一下记忆化操作。

  1. // 记忆化模板
  3. int g[MAXN];  // 定义记忆化数组
  4. int ans = 最坏情况, now;
  5. void dfs f(传入数值) {
  6.     if (g[规模] != 无效数值) return;  // 或记录解，视情况而定
  7.     if (到达目的地) ans = 从当前解与已有解中选最优;  // 输出解，视情况而定
  8.     for (遍历所有可能性)
  9.         if (可行) {
  10.             进行操作;
  11.             dfs(缩小规模);
  12.             撤回操作;
  13.         }
  14. }
  16. int main() {
  17.     memset(g, 无效数值, sizeof(g));  // 初始化记忆化数组
  19. }