张伦聪的技术博客 Research And Development

递归,迭代,动态规划的区别

2018-07-25

题目:有n步台阶,一次只能上1步或者2步,共有多少种走法?

经典题目来区别这三种常见解题方法的异同。

解1:递归

 public int method1(int n) {
        //递推公式:f(n)=f(n-1)+f(n-2);
        //初始化:f(1)=1;f(2)=2;
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        return method1(n - 1) + method1(n - 2);
    }

解2:迭代

    public int method2(int n) {
        int first = 1;
        int second = 2;
        int third = 0;
        for (int i = 3; i <= n; i++) {
            third = first + second;
            first = second;
            second = third;
        }
        return third;
    }

解3:动态规划

    public int method3(int n) {
        int[] tmp = new int[n];
        //初始化
        tmp[0] = 1;
        tmp[1] = 2;
        for (int i = 2; i < n; i++) {
            //定义状态
            tmp[i] = tmp[i - 2] + tmp[i - 1];
        }
        return tmp[n - 1];
    }

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

¥ 打赏博主

类似文章

留言