码农乌托邦

楠哥小站

楠哥,理想主义码农,就职于Google,现居纽约。


Climbing Stairs

爬楼梯问题是一道典型的递归问题和动态规划问题的入门级题目。题目描述是:给定一个n个台阶楼梯,每次可以上一个或者两个台阶,请问最终可以有多少种方法爬到顶层。使用递归的思路解决是,到达第K个楼梯的方法数目是到达地k-1个楼梯的方法数与到达地k-2的楼梯的方法数的和。所以,如果函数原型是int cal(int n),那么我们可以得到递归规则是cal(k)=cal(k-1)+cal(k-2)。边界条件是cal(1)=1,cal(2)=2。但是,这样计算会有很多的重复性计算,所以可以使用动态规划来解决。如果使用一位数组ways来存储到达第k个楼梯的方法数,那么ways[k+1] = ways[k]+ways[k-1];从0一直结算到n,可以避免很多的重复计算。该题目是leetcode上OJ的题目,也是CtCI的原题的变形。下面是给题目的Java实现。

public class Solution {

	/**
	 * You are climbing a stair case. It takes n steps to reach to the top.
	 * Each time you can either climb 1 or 2 steps. In how many distinct 
	 * ways can you climb to the top?
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(new Solution().climbStairs(10));

	}
	
	public int climbStairs(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
		
		if(n < 0)
			return 0;
		
		int[] ways = new int [n+1];
		
		ways[0] = 1;
		ways[1] = 1;
		
		for(int i = 2; i < n+1; i++){
			ways[i] = ways[i-1]+ways[i-2];
		}		
		return ways[n];        
       }

}
最近的文章

Valid Parentheses

括号题目是一类经典的算法题目,有很多变形。这类题目乍一看上去没有什么思路,但是实质上就是最近成对括号的匹配问题。常用的方法有记录括号数目和使用栈两种方式。 合法括号的判断问题是指在一串由()[]和{}…

Technical, Career继续阅读
更早的文章

Balanced Binary Tree

判定平衡二叉树的题目是一道基本的数据结构题目,在Leetcode的OJ上也有相关的测试用例。二叉树的结构请参见《Leetcode中使用的二叉树结构》。 可以使用一个递归函数,递归的判断每个节点的左子树…

Technical, Career继续阅读
comments powered by Disqus