问题描述

有个小孩在上楼梯，楼梯有N阶，小孩一次可上1阶、2阶、3阶。实现一个算法，计算小孩有多少种上楼梯的方式。输入n返回一个整数。

思路

当楼梯只有一阶时，只有一种方法(1)
楼梯有两阶时，有两种方法(1)(2)
当楼梯有三阶时，有四种方法(111)(12)(21)(22)
当楼梯有n阶时，最后一次上楼的方法为(n-1)+(n-2)+(n-3)

解

namespace ChildStairs
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(CheckCountWays(4));
        }

        static int CheckCountWays(int n)
        {
            if (n == 1) return 1;
            if (n == 2) return 2;
            if (n == 3) return 4;
            return CheckCountWays(n-1)+ CheckCountWays(n-2)+ CheckCountWays(n - 3);
        }
    }
}

思考

使用递归的方式虽然简单，但效率低，可以采用备忘录式的动态规划进行优化

优化后的解

namespace ChildStairs
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(CountWays(4));
        }

        static int CountWays(int n)
        {
            Dictionary<int, int> dic = new Dictionary<int, int>();
            return CountWaysDP(n, dic);
        }

        static int CountWaysDP(int n,Dictionary<int,int> dic)
        {
            if (n == 1) return 1;
            if (n == 2) return 2;
            if (n == 3) return 4;
            if (dic.ContainsKey(n)) return dic[n];
            dic.Add(n, CountWaysDP(n - 1,dic) + CountWaysDP(n - 2,dic) + CountWaysDP(n - 3,dic));
            return dic[n];
        }
    }
}