首页 > 代码库 > 动态规划分析总结——怎样设计和实现动态规划算法

动态规划分析总结——怎样设计和实现动态规划算法

进行算法设计的时候,时常有这种体会:假设已经知道一道题目能够用动态规划求解,那么非常easy找到对应的动态规划算法并实现;动态规划算法的难度不在于实现,而在于分析和设计—— 首先你得知道这道题目须要用动态规划来求解。

本文,我们主要在分析动态规划在算法分析设计和实现中的应用,解说动态规划的原理、设计和实现。在非常多情况下,可能我们能直观地想到动态规划的算法。可是有些情况下动态规划算法却比較隐蔽。难以发现。

本文。主要为你解答这个最大的疑惑:什么类型的问题能够使用动态规划算法?应该怎样设计动态规划算法?

                                                                             动态规划第一讲——缓存与动态规划

一、缓存与动态规划


例一:有一段楼梯有10级台阶。规定每一步仅仅能跨一级或两级,要登上第10级台阶有几种不同的走法?


分析:非常显然,这道题的相应的数学表达式是F(n)=F(n-1) + F(n-2);当中F(1)=1, F(2)=2。

非常自然的状况是,採用递归函数来求解:

int  solution(int n){
	if(n>0 && n<2) return n;
	return solution(n-1) + solution(n-2);
}


    假设我们计算F(10), 先须要计算F(9) F(8); 可是我们计算F(9)的时候,又须要计算F(8),非常明显,F(8)被计算了多次。存在反复计算;同理F(3)被反复计算的次数就很多其它了。算法分析与设计的核心在于 依据题目特点,降低反复计算。  在不改变算法结构的情况下。我们能够做例如以下改进:
int dp[11];
int  solution(int n){
	if(n>0 && n<2) return n;
	if(dp[n]!=0) return dp[n];
	dp[n] = solution(n-1) + solution(n-2);
	return  dp[n];
}
这是一种递归形似的写法,进一步,我们能够将递归去掉:
int  solution(int n){
	int dp[n+1];
	dp[1]=1;dp[2]=2;
	for (i = 3; i <= n; ++i){
		dp[n] = dp[n-1] + dp[n-2];
	}
	return  dp[n];
}
当然,我们还能够进一步精简。只用两个变量来保存前两次的计算结果; 这个算法留待读者自己去实现

例二:01背包问题

有n个重量和价值分别为vector<int> weight, vector<int> value的物品;背包最大负重为W,求能用背包装下的物品的最大价值?

输入:n =4 
weight=2, 1, 3, 2
value =http://www.mamicode.com/3, 2, 4, 2
W=5
输出=7


思考一:我们能够採用穷举法,列出n个物品的全部组合形式,从中选取符合条件的最大价值:

採用穷举法,必定须要可以举出全部状态,不重不漏;而怎样穷举,方法多种多样,我们的任务是要穷举有n个元素组成的全部子集。

而穷举的方法主要有两种—— 递增式(举出1~100之内的全部数字, 从1到100);和分治式的穷举(比如举出n个元素的集合。包括两种—— 含有元素a和不含元素a的)。于是,我们基于穷举法得到背包问题的第一种算法—— 递归与分治。

int rec(int i, int j){//从i到n号物品,选择重量不大于j的物品的最大价值
	int res;
	if(i==n){
		res=0;
	} 
	else if(j< w[i]){
		res = rec(i+1, j);
	}
	else{
		res = max(rec(i+1, j), rec(i+1, j-w[i])+v[i]);
	}
	return res;
}

调用res(0, W), 就可以得到结果. 时间复杂度O(2^n);我们来分析一下递归调用的情况。

技术分享

为了偷懒,最后一行没有画出来,可是注意红色的部分。我们会

动态规划分析总结——怎样设计和实现动态规划算法