70. Climbing Stairs【leetcode】递归,动态规划,java,算法

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?

Note: Given n will be a positive integer.

题目分析:每次只能走1或2步,问n步的话有多少中走法????

可以用动态规划和递归解决,提交代码过程中可能会出现n过大时,时间超时的提示,这个时候我们就要考虑时间复杂度了。

预备知识:递归和动态规划和分治法都有什么关系?

  1. 动态规划实现:时间和空间复杂度都是最大O(n),代码和运行时间如下图
public class Solution {
public int climbStairs(int n) {
if (n == 1) {
return 1;
}
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}

70. Climbing Stairs【leetcode】递归,动态规划,java,算法

Fibonacci Number算法 时间为O(n)空间为O(1)

public class Solution {
public int climbStairs(int n) {
if(n==1){
return 1;
}
int first=1;
int second=2;
for(int i=3;i<=n;i++){
//f(3)=f(2)+f(1);
//f(4)=(f3)+f(2); int third =0;
third=first+second;
first=second;
second =third;
}
return second;
} }

这里给出运行时间

70. Climbing Stairs【leetcode】递归,动态规划,java,算法

递归法实现()

public class Solution {
public int climbStairs(int n) {
int mem[] =new int[n+1];
return climb(0,n,mem);
}
public int climb(int i,int n,int mem []){ if(i>n){
return 0;
}
if(i==n){
return 1;
}
if(mem[i]>0){
return mem[i];
}
mem[i]=climb(i+1,n,mem)+climb(i+2,n,mem);
return mem[i];
}
}

1、分治策略(Divide and Conquer)

将原问题分解为若干个规模较小但类似于原问题的子问题(Divide),递归的求解这些子问题(Conquer),然后再合并这些子问题的解来建立原问题的解。因为在求解大问题时,需要递归的求小问题,因此一般用递归的方法实现,即自顶向下。

2、动态规划(Dynamic Programming)

动态规划其实和分治策略是类似的,也是将一个原问题分解为若干个规模较小的子问题,递归的求解这些子问题,然后合并子问题的解得到原问题的解。区别在于这些子问题会有重叠,一个子问题在求解后,可能会再次求解,于是我们想到将这些子问题的解存储起来,当下次再次求解这个子问题时,直接拿过来就是。其实就是说,动态规划所解决的问题是分治策略所解决问题的一个子集,只是这个子集更适合用动态规划来解决从而得到更小的运行时间。即用动态规划能解决的问题分治策略肯定能解决,只是运行时间长了。因此,分治策略一般用来解决子问题相互对立的问题,称为标准分治,而动态规划用来解决子问题重叠的问题

动态规划一般由两种方法来实现,一种为自顶向下的备忘录方式,用递归实现,一种为自底向上的方式,用迭代实现。

3、贪心算法(Greedy Algorithm)

贪心算法在每一步都做出最优的选择,希望这样的选择能导致全局最优解。对,只是寄希望,因此贪心算法并不保证得到最优解,但是它对很多问题确实可以得到最优解,而且运行时间更短。由此可见,贪心算法是带有启发性质的算法。那什么时候可以用贪心算法呢?当该问题具有贪心选择性质的时候,我们就可以用贪心算法来解决该问题。 
贪心选择性质:我们可以通过做出局部最优(贪心)来构造全局最优。只要我们能够证明该问题具有贪心选择性质,就可以用贪心算法对其求解。比如对于0-1背包问题,我们用贪心算法可能得不到最优解(当然,也可能会得到最优解),但对于部分背包问题,则可以得到最优解,贪心算法可以作为0-1背包问题的一个近似算法。

动态规划与递归的比较

就性能而言,我用递归和动态规划实现了斐波纳契数列计算,递归如果超过40的时候就已经需要很长时间了,40次大概需要1秒左右,但是用动态规划要一亿次,才需要4秒,这个相差的可不是几个数量级的问题。事实上,递归实现的斐波那契数列计算时间复杂度为O(2ⁿ),动态规划实现时间复杂度为O(n)所以,在以后的开发中,尽量避免使用递归。 
就具体实现上而言,动态规划比普通递归仅仅是多了一步保存子问题计算结果的操作。 
例如,斐波那契数列的递归实现如下:

 int F(int i)
{
if(i < 1) return 0;
if(i == 1) return 1;
return F(i-1) + F(i - 2);
}
  • 而用动态规划算法实现是这样:
 int F(int i)
{
if(knownF[i] != unknown){
return knownF[i];
}
if(i == 0) t = 0;
if(i == 1) t = 1;
if(i > 1) t = F(i - 1) + F(i - 2);
return knownF[i] = t;
}

4、总结

  1. 分治策略用于解决原问题与子问题结构相似的问题,对于各子问题相互独立的情况,一般用递归实现;
  2. 动态规划用于解决子问题有重复求解的情况,既可以用递归实现,也可以用迭代实现;
  3. 贪心算法用于解决具有贪心选择性质的一类问题,既可以用递归实现,也可以用迭代实现,因为很多递归贪心算法都是尾递归,很容易改成迭代贪心算法;
  4. 递归是实现手段,分治策略是解决问题的思想,动态规划很多时候会使用记录子问题运算结果的递归实现。

参考资料: 
1.http://1661518.blog.51cto.com/1651518/1396943 
2.《算法导论》第三版

3.http://blog.csdn.net/tyhj_sf/article/details/53969072

 
 
上一篇:dotnet 通过 WMI 获取设备厂商


下一篇:java for循环里面执行sql语句操作,有效结果只有一次,只执行了一次sql mybatis 循环执行update生效一次 实际只执行一次