【漫画】什么是动态规划？

如果累了的话，不妨看一下超可爱的漫画吖

来源：伯乐专栏作者/玻璃猫，微信公众号 - 梦见

主页君小提示：图文有点长，慢慢看，做好防查颓措施

问题

现在有$10$级台阶，要求从第一阶向上走，每一次可以走一步或走两步，求有多少种不同走法。

比如说我们可以一阶一阶的走，一共走10步。这是一种走法。

就像这样：

再或者我们可以两步两步的走，一共5步。就像这样：

当然啦，除此之外，还有很多种走法……

第一种情况

第二种情况

$F(0) = 0;$
$F(1) = 1;$
$F(2) = 2;$
$F(i) = F(i - 1) + F(i - 2)$

int work(int i){
	if(i == 0){
		return 0;
	}
	else if(i == 1){
		return 1;
	}
	else if(i == 2){
		return 2;
	}
	else{
		return work(i - 1) + work(i - 2);
	}
}

(其实备忘录算法在OI上一般叫记忆化搜索)

int work(int i){
	int a[10001]
	if(i == 0){
		return 0;
	}
	else if(i == 1){
		return 1;
	}
	else if(i == 2){
		return 2;
	}
	int a = 1;
	int b = 2;
	int temp = 0;
	for(int i = 3; i <= n; i ++){
		temp = a + b;
		a = b;
		b = temp;
	}
	return temp;
}

问题

有一个国家发现了5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。

参与挖矿工人的总数是10人。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。

要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？

每一座金矿都有挖与不挖两种选择，如果有N座金矿，排列组合起来就有2^N种选择。

对所有可能性做遍历，排除那些使用工人数超过10的选择，在剩下的选择里找出获得金币数最多的选择。

代码比较简单就不展示了，时间复杂度也很明显，就是O(2^N)。

F(n,w) = 0 (n<=1, w < p[0]);

F(n,w) = g[0] (n==1, w >= p[0]);

F(n,w) = F(n-1,w) (n>1, w < p[n-1])

F(n,w) = max(F(n-1,w), F(n-1,w-p[n-1])+g[n-1]) (n>1, w >= p[n-1])