递归–递推–动态规划
首先，我的理解这三种都是一种形式、一个思想。包括递推、dp都可以算作是递归。用递归的形式，代码简洁，但是效率低（改进，记忆性递归）。dp，递推代码比较多，但是效率高
下面看我学的几个例题：
上楼梯
题意：小明上楼梯，他一次能上一层、两层、或者三层，问100层楼梯，有多少种走法
- 递归分析：每在一层楼都可以分为三种情况，往上走1、走2、走3。反之，每一层都是由三种走上来的。由下面一层、下面两层、下面三层走上来。所以，往下递归，每一层都有三种情况：n-1,n-2,n-3
- 递推分析:每一层都是由三种情况得出，那么就可得出递推公式 fn=fn-1+fn-2+fn-3;
- 代码如下：
public class 上楼梯 { public static void main(String[] args) { int n=8 ; int t=fbs1(n); int a=fbs2(n); System.out.println(t); System.out.println(a); } //递推 private static int fbs2(int n) { if(n<0) return 0; if(n==1||n==0) return 1; if(n==2) return 2; if(n==3) return 4; int x1=1,x2=2,x3=4; for (int i = 4; i <= n; i++) { int t=x1; x1=x2; x2=x3; x3=x1+x2+t; } return x3; } //递归 private static int fbs1(int n) { int m=0; if(n==1||n==0) return 1; if(n==2) return 2; m+=fbs1(n-1); m+=fbs1(n-2); m+=fbs1(n-3); return m; } }
未完待续
