C#递归求解楼梯问题优化方案

刀锋狼

Q : 楼梯有N（小于50的整数）阶，上楼可以一步上一价，也可以一次上二阶。编一个程序，计算共有多少种不同的走法。(递归实现)

方法一、
public long ladder(int num)
{
     if (num == 1) return 1;
     if (num == 2) return 2;
     return ladder(num - 1) + ladder (num - 2);
}
方案一简单粗暴，也是网上大部分解决此问题的方法，但是，当num值超过50时，就需要等待一分多钟才能求出结果，数值越大，越慢。
因此，必须对递归算法进行优化。方案：用数组arr[n] 记录当num = n时，递归调用后的返回值（此返回值确保不为0），当下次递归调用方法时判断 arr[n]是否不为0（因为arr初始化为0），如过不为0，说明已经递归计算过arr[0]的值了，没有必要再次进行漫长的递归计算，直接返回arr[n]的值即可。
C#代码如下，优化后，速度提高 n 倍：

class MainClass
{
        public long[] arr;
        public static void Main(string[] args)
        {
                //输入的数越大越明显，如：50
            Console.Write("请输入阶梯数 : ");
            MainClass mc = new MainClass();
            int n = Convert.ToInt32(Console.ReadLine());
            mc.arr = new long[n + 1];
            long m = mc.TaiJie(n);
            Console.WriteLine(n + " 个阶梯，共有 " + m + " 种不同走法");
        }
        public long TaiJie(int num)
        {
            if(num == 1){
                return 1;
            }
            if(num == 2){
                return 2;
            }
            if(0 != arr[num]){
                return arr[num];
            }
            arr[num - 1] = TaiJie(num - 1);
            arr[num - 2] = TaiJie(num - 2);
            return arr[num - 1] + arr[num - 2];
        }
}

HIDEOKOJIMA

Thanks for sharing this one !