初识动态规划

斐波那契数列大家一定很熟悉吧**【f(n)=f(n-1)+f(n-2)】**，如果要通过代码来表达斐波那契数列也是很简单的，只需要一个简易的递归即可。但是由于递归的一些缺陷，自然有人会写出迭代方式

int Fun(int n){
	if(n==1 || n==2)
		return 1;
	first=1;
	second=1
	third=0;
	while(n>2){
		third=first+second;
		first=second;
		second=third;
		n--;
	}
	return third;
}

迭代版本如上图👆：

我们会发现，所求的第n个斐波那契数的值与第n-1个和第n-2个值密切相关，每次的循环三者的值都会一起得到更新，最终达到临界值就是答案。像这种算法我们称之为动态规划

对于动态规划的题目，一般有一个固有的步骤。

1、定义状态方程

2、构建状态转移方程

3、设置初始值

下面我们通过具体题目来感受dp算法

https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4?

tpId=13&tqId=11161&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

青蛙跳台问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）

这个问题我们需要一定的逆向思维

分析：

青蛙到第n级台阶的上一步在第n-1级或者第n-2级

到第n-1级的上一步在第n-2级或第n-3级

到第n-2级的上一步在第n-3级或第n-4级

………………………………

到此我们可以发现规律，到达第n级台阶的方法无非是到达第n-1级和到达第n-2级的方法之和

因此我们可以先完成第一步，定义状态方程f（n），表示到达第n级台阶的方法数

第二步，我们需要把求第n级台阶方法数的问题转变为求第n-2级和第n-1级台阶方法数（以此类推）

于是求出状态转移方程

f（n）=f（n-1）+f（n-2）

最后就需要设初值了，由于n>=2时转移方程才有意义，因此初始值就是为n=1和n=0所设置了

规定f(1)=f(0)=1

int jumpFloor(int number){
	if(number=2){
		third=first+second;
		first=second;
		second=third;
		n--;
	}
	return third;

(会发现其实这就是一个斐波那契数列问题的实际应用)

矩形摆放问题

https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6?

tpId=13&tqId=11163&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/questionranking

我们可以用 2 * 1 的小矩形横着或者竖着去覆盖更大的矩形。请问用n个 2 * 1 的小矩形无重叠地覆盖一个 2*n 的大矩形，总共有多少种方法？

分析：

类似于青蛙跳台

要形成2n的矩形的方式无非是以下两种情形方法数之和

1、在2（n-1）的矩形上竖放一个2 * 1矩形

2、在2*（n-2）的矩形上横放两个2 * 1矩形

因此可以很快的定义出状态方程f（n）

f（n），代表形成2*n矩形的方法数

从而写出状态转移方程

f（n）=f（n-1）+f（n-2）

最后设置初始值

f(1)=1,f(2)=2

这样问题就变成一种类斐波那契数列的数学递推。

最长子序列问题

https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?

tpId=13&tqId=11183&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。

我们依旧可以借鉴前两题的思想，试着去定义状态方程

f(array[i])可以看作是以array[i]为结尾的一个子序列和

自然需要把问题向前推，如果array[i-1]+array[i]的值大于array[i]，那么i-1~i就有可能是一个答案，当遇到某个值添加之后序列减小，就可以得出以array[i]为尾的最长子序列了

状态转移方程：f(n)=max(f(n)+f(n-1),f(n))

设置初始值：以array[0]为尾的最长子序列就是本身

int FindGreatestSumOfSubArray(vector& array){
	vector dp(array.size(),0);
	dp[0]=array[0];			//设初值
	int maxsum=dp[0];		//记录当前最长子序列
	for(int i =1 ; i maxsum)
			maxsum=dp[i];
	}
	return maxsum;
}

手机扫描二维码访问