斐波那契系列问题的递归和动态规划
题目一：返回斐波那契数列的第N项
斐波那契数列的形式可以表示为：1,1,2,3,5,8......，也就是除了第一项和第二项为1外，第N项F(N)=F(N-1)+F(N-2)，可以写出暴力递归代码，时间复杂度为O(2^N)
斐波那契数列
题目二：给定整数N，代表台阶数，一次可以跨2个或者1个台阶，返回多少种走法
如果台阶只有一级，只有一种走法；如果台阶有两级，走法有两种；如果台阶有N级，最后跳上第N级的情况，要么是从N-2级直接跳两级台阶，或者从第N-1级跳一级台阶，所以台阶有N级的方法数等于跨到N-2级台阶的方法数加上跨到N-1级台阶的方法数，即S(N)=S(N-1)+S(N-2),初始项为S(1)=1,S(2)=2,类似于斐波那契数列，只不过是初始项不同。
跳台阶问题
题目三：假设农场中成熟的母牛每年只会生1头小母牛，并且永远都不会死。第一年农场有一只成熟的母牛，从第二年开始，母牛开始生小母牛。每只小母牛三年以后成熟又可以生小母牛。给定整数N，求N年后母牛的数量
所有的牛都不会死，所以第N-1年的牛会活到第N年；那么成熟的牛的数量该如何估计呢，就是N-3年的牛的数量，期间出生的牛都不会成熟，所以C(N)=C(N-1)+C(N-3)，初始项为C(1)=1,C(2)=2,C(3)=3,又是类似于斐波那契数列，代码如下：
母牛问题
矩阵的最小路径和
题目：给定一个矩阵m，从左上角开始每次只能向右或者向下走，最后达到右下角的位置，路径上所有数字累加起来就是路径和，返回所有路径中最小的路径和
假设现在有如下矩阵：
矩阵
那么1,3,1,0,6,1,0就是最短路径。
这是一道经典的动态规划问题。假设矩阵m的大小为MxN，行数为M，列数为N。先生成大小和m一样的矩阵dp，dp[i][j]的值表示从左上角走到[i][j]位置的最小路径和。对于m的第一行的所有位置来说，从(0,0)位置到(0,j)位置只能往右走，所以(0,0)位置到(0,j)位置的路径和就是m[0][0...j]这些值的累加结果。同理，对于m的第一列的所有位置来说，从(0,0)位置走到(i,0)位置只能往下走。
dp矩阵
除第一行和第一列外，每一个位置都要考虑从左边到达自己的路径和最小还是从上边到达自己的路径和最小。最右下角的值就是整个问题的解。动态规划代码如下所示：
矩阵最小路径和
在这个算法中，时间复杂度为O(MxN)，额外的空间复杂度为O(MxN)。
换钱最少的货币数
给定数组arr，arr中所有的值都为正数且不重复，每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个正数aim代表要找的钱数，求组成aim的最少货币数
该问题的经典动态规划方法。如果arr的长度为N，生成行数为N，列数为aim+1的动态规划表dp。dp[i][j]的含义是在可以任意使用arr[0...i]货币的情况下，组成j所需的最小张数。根据这个定义，dp[i][j]的值的计算方法如下：
- 当列数为0即在第一列上，表示找到钱数为0时需要的最小张数，易得结果为0
- 当行数为0即在第一行上，表示在只能使用arr[0]货币的情况下，找某个钱的最小张数。比如，arr[0]=2，那么能找开的钱数为2,4,6,8......所以令dp[0][2]=1，dp[0][4]=2，dp[0][6]=3，第一行其他位置代表的钱数一律找不开，所以一律设为32位整数的最大值，我们设这个值为max。
- 剩下的位置依次从左到右，再从上到下计算。假设计算到位置(i,j)，那么dp[i,j]的值可以简化为来自下面的情况：
- 第一种情况就是使用arri货币，那么结果就变成了求dp[i][j-arr[i]]+1
- 第二种情况就是不使用arr[i]货币，那么结果就变成了求dp[i-1][j]
-
最后选择上述情况中较小的值最为最终dp[i][j]的解，所以dp[i][j]=min{dp[i-1][j]，dp[i][j-arr[i]]+1}
如果j-arr[i]<0，即发生越界了，说明arr[i]太大，用一张都会超过钱数j，令dp[i][j]=dp[i-1][j]即可，具体代码如下，时间复杂度和额外空间复杂度都为O(Nxaim):
换钱最少的货币数
网友评论