[数据结构与算法]动态规划算法爬楼梯

@TOC动态规划算法

动态规划算法-爬楼梯

题目描述

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

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
实例1
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。

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

解题思路

通过对题目进行分析
F(1) 1
F(2) 2
F(3) 3
F(4) 5
从而得到它的规律为
F(n)= F(n-1)+F(n-2)
将转化为y转移方程。采用滚动数组思想来实现。

题解

package com.worK;

import java.util.Scanner;

public class climbStairs {
    public static void main(String[] args) {
        dusolution arg = new dusolution();
        Scanner sc = new Scanner(System.in);
        System.out.println("输入需要n阶你才能到达楼顶");
        int i = sc.nextInt();
        System.out.println(arg.climb(i));

    }
}
class dusolution{
    public int climb(int n){
        int p = 0,q=0,r=1;
        for(int i=0;i<n;i++){
            p = q;
            q = r;
            r = p+q;
        }
        return r;
    }
}