C语言入门算法——爬楼梯（了解动态规划）

题目描述：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

• 1 <= n <= 45

  题目来源：爬楼梯

  思路及部分代码：

  1. 分析

          通过题目我们可以了解到 f(n) 的方法是上一台阶 f(n-1) ——爬一阶台阶到达 f(n)  加上上两阶台阶到达 f(n) 。所以可得 f(n) = f(n - 1) + f(n-2)；

  2. dynamic() 直接递归（超时）

          此函数重复计算，导致时间不够。

  int dynamic(int n){
      if(n == 1) return 1;
      else if(n == 2) return 2;
      else{ //大于阶梯数
          //方法有 f(n) = f(n -1) + f(n - 2);
          return dynamic(n-1) + dynamic(n-2);
      }
  }

  3. dynamic_1(); 从1到n（通过）

          通过从1计算到n并保存之前的f(n-1) 和f(n-2)

  int dynamic_1(int i, int a1, int a2,int n){
      if(i == 1){
          a1 = 0;
          a2 = 1;
      }
      if(i >= n) return a1+a2;
      else return dynamic_1(i+1, a2, a1+a2,n);
  }

  4. dynamic_2();  数组 （通过）

          在了解动态规划时，看见要用数组，就想到了这样，显示这种和dynamic_1();的方法一样，只是将a1,a2；改成了数组而已。（不是动态规划）

  int num[3] = {0,0,0};
  int dynamic_2(int i, int n){
      //更新数据
      if(i == 1){
          num[0] = 0;
          num[1] = 1;
          num[2] = num[0] + num[1];
      }
      else{
          num[0] = num[1];
          num[1] = num[2];
          num[2] = num[0] + num[1];
      }
      if(i >= n) return num[2];
      else return dynamic_2(i+1,n);
  }

  5. dynamic_3();  动态规划 （通过）

          动态规划算法：（百度）核心思想是将问题分解为若干个子问题，并保存这些子问题的解，以便在解决原始问题时可以重复使用，避免重复计算，从而提高算法的效率。动态规划特别适用于那些具有“最优子结构和重叠子问题”特性的问题，在动态规划中，原问题被分解为相对简单的子问题，这些子问题按顺序求解，并通过保存它们的解来避免重复计算，最终通过组合这些子问题的解来得到原问题的解。

          理解：1. 减少重复计算        2.用小问题叠加解决大问题

  //动态规划
  int dynamic_3(int n){
      int dp[n+1];
      dp[0] = 1;
      dp[1] = 1;
      for(int i = 2; i 
  总代码：
   
  int dynamic(int n){
      if(n == 1) return 1;
      else if(n == 2) return 2;
      else{ //大于阶梯数
          //方法有 f(n) = f(n -1) + f(n - 2);
          return dynamic(n-1) + dynamic(n-2);
      }
  }
  int dynamic_1(int i, int a1, int a2,int n){
      if(i == 1){
          a1 = 0;
          a2 = 1;
      }
      if(i >= n) return a1+a2;
      else return dynamic_1(i+1, a2, a1+a2,n);
  }
  int num[3] = {0,0,0};
  int dynamic_2(int i, int n){
      //更新数据
      if(i == 1){
          num[0] = 0;
          num[1] = 1;
          num[2] = num[0] + num[1];
      }
      else{
          num[0] = num[1];
          num[1] = num[2];
          num[2] = num[0] + num[1];
      }
      if(i >= n) return num[2];
      else return dynamic_2(i+1,n);
  }
  //动态规划
  int dynamic_3(int n){
      int dp[n+1];
      dp[0] = 1;
      dp[1] = 1;
      for(int i = 2; i 
  总结：
   
          了解动态规划，减小运行时间，在题目越来越难的情况下，原本的暴力手段已经不足以解决问题，只有通过学习不同的算法才能完成更高难度的题目，以下是本次总结。
   
  不足之处：
   
   
  递归方法 (dynamic 和 dynamic_1)：
   
  使用递归方式解决问题，但存在效率问题，特别是对于较大的输入值。
  在 dynamic_1 中，变量传递方式可能不够清晰。
   
  递归方法使用全局变量 (dynamic_2)：
   
  使用全局变量 num 来存储中间结果，避免了重复计算。
  全局变量的使用增加了代码的复杂性和维护难度。
   
  动态规划方法 (dynamic_3)：
   
  使用动态规划来解决问题，避免了递归中的重复计算问题。
  效率较高，适用于大规模问题的解决。
   
  改进建议：
   
   
  优化效率：
   
  对于递归方法，考虑使用记忆化搜索来避免重复计算，提高效率。
   
  改进代码结构：
   
  改进变量传递方式，使代码更清晰易懂。
  避免使用全局变量，可以通过参数传递或者结构体来管理状态。
   
  代码质量提升：
   
  添加适当的注释和更具描述性的命名，以提高代码的可读性。
  实现错误处理机制，确保代码的健壮性和稳定性。
   
  参考资料：
   
  看一遍就理解：动态规划详解