算法问题解决——动态规划法

1、斐波那契数列

（1）自底向上：通过填表格的方式，给出a[0]=0,a[1]=1,其他的数组元素通过a[n]=a[n-1]+a[n-2]得到。

（2）自顶向下：自顶向下是采取备忘录的方式，求a[n],则需要求a[n-1]与a[n-2],而得到a[n-1]与a[n-2]又需要利用递归继续向下求解。

     2、走棋盘：走棋盘问题，因为只能向下或者向右走，所以在走最后一步时，a[i][j]的走法为a[i-1][j]的走法与a[i][j-1]走法的和，然后利用递归以此类推，可以得到总共的走法。

     3、爬台阶问题：在到达最后一层楼梯时，可以选择走一步或者两步，所以最后一层走法为走一步的方法加上走两步的方法，以此类推，通过递归可以得到爬台阶的总走法。

四、问题解决

     1、斐波那契数列getFibByMe（）

      （1）自底向上

输入：n

输出：第n个数的值

过程：1.定义一个空白数组fib[ ]，长度为100

2.将0赋值给数组的第一个元素，将1赋值给数组的第二个元素。

3.定义循环变量并初始化为0；

4.i从2循环到n，并重复执行以下操作

 4.1 fib[i]=fib[i-1]+fib[i-2];

5. 返回fib[n];

时间复杂度：O(n)

代码实现：

结果：

  （2）自顶向下

输入：i

输出：斐波那契数列中对应下标为i的数

过程：1.定义一个空白数组fib[ ],长度为100

2.如果i<=1,fib[i]=I;

3.否则

3.1如果fib[i-2]<=0,则fib[i-2]=getFibBiMen(i-2);

3.2如果fib[i-1]<=0,则fib[i-1]=getFibByMen(i-1);

3.3fib[i]=fib[i-2]+fib[i-1];

4.返回 fib[i];

时间复杂度：O(n)

代码实现：

结果：

     2、走棋盘getPath（）

输入：棋盘的行数n，列数m。

输出：走的路径总数

过程：1。定义一个二维数组a[ ][ ],长度为m，n

2．定义循环变量i，j并初始化为0

3．i从0循环到m，并重复执行以下操作

 3.1 a[1][i]=1;

 3.2 i++;

4.j从1循环到m，并重复执行以下操作

 4.1 a[j][0]=1;

 4.2 j++;

5. i从2循环到n，并重复执行以下操作

 5.1 j从2循环到m，并重复循环以下操作

 5.1.1 a[i][j]=a[i-1][j]+a[i][j-1];

 5.1.2 j++;

 5.2 i++;

6.return a[n-1][m-1];

时间复杂度：O(n*m)

代码实现：

结果：

     3、爬台阶问题upStairs（）

输入：楼梯的阶数n

输出：爬台阶一共的解法

过程：1.定义一个空的数组a[ ],长度为n

2.如果n<=0,则返回0；

3.a[0]=1;a[1]=2;

4.定义循环变量并初始化为0

5.i从2循环到n，并重复执行以下操作

 5.1a[i]=a[i-1]+a[i-2];

6.返回a[n-1]；

时间复杂度：O(n)

代码实现：

结果：