动态规划

矩阵连乘问题

#include<iostream>

using namespace std;

int main(){
	int n;
	cin >> n;
	int a[n+1];
	for(int i = 0; i <= n; i++) cin >> a[i]; 
//将输入从i = 1，改为i = 0， 就通过了，还未搞通
	int d[100][100];
	int dt;
	for(int i = 1; i <= n; i++) d[i][i] = 0;
	 for(int dis = 1; dis < n; dis++){
	 	for(int i = 1, j = 1+dis; j <= n; i++, j++){
	 		d[i][j] = 3242424;
	 		for(int k = i; k < j; k++){
	 			dt = d[i][k]+d[k+1][j]+ a[i-1]*a[k]*a[j];
				 if(dt < d[i][j]){
				 	d[i][j] = dt;
				 }		
			 }
		 }
	 }
	 cout << d[1][n];
}

数字三角形

#include<iostream>
#include<algorithm> 
#include<cstring>
using  namespace std;
int d[100][100];
int a[100][100];int n;
int ds(int i, int j){
	if(d[i][j] >= 0) return d[i][j];
	return d[i][j] = a[i][j]+(i == n?0:max(ds(i+1, j), ds(i+1, j+1) )); 
}

int main(){
	cin >> n;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < i+1; j++)
			cin >> a[i][j]; 
	}
	memset(d, -1, sizeof(d));
	cout << ds(0,0); 
}

红鲤鱼与绿鲤鱼

第15周任务-红鲤鱼和绿鲤鱼
时间限制：1秒 内存限制：128兆
7 次提交 2 次通过
题目描述
Polarbear（P.B.）有很多红鲤鱼和绿鲤鱼，它们在鱼缸排成一列，非常好看。P.B.可以任选一条鲤鱼把它染成红色或
绿色，它的目标是在完成染色之后，让每条红色的鲤鱼R都比绿色的鲤鱼G离左侧更近（当然当所有鲤鱼颜色都相同
时，很显然也满足这个条件）。P.B.想知道它最少需要涂染几条鲤鱼。

如样例所示: s = RGRGRR
我们涂染之后变成RRRRRR就满足要求了,涂染的个数为2,没有比这个更好的涂染方案。
输入
输入包括一个字符串s,字符串s长度length(1<=length<=50),其中只包括'R'或者'G',分别表示红鲤鱼和绿鲤鱼。
输出
输出一个整数,表示P.B.最少需要涂染的鲤鱼的数量。
样例输入
RGRGRR
样例输出
2
题目分析：
本题也是一道动态规划思想的题目，每次有两种选择，在所有选择中找最优选择方案。由于这题数据范围比较小。所有大部分人暴力的方法用双重循环遍历所有选择方案，最后也能解决问题。这是方法的时间复杂度是O（n^2），但是如果我给的字符串长度超过了10000，这种方法基本就无法解决问题了。这里我用动态规划的思想给出一种O（n）的解决方法。可以参照你们的解法和我的解法的区别，体会动态规划的思想和暴力解法的不同之处。

如何推导出状态转移方程式动态规划的难点，例如本题的状态转移方程就是:
dp[1][i] = min(dp[0][i-1]), dp[1][i-1]) + (str[i] == ‘G’ ? 0 : 1);
即第i次染色的最少染色次数为：[0,i-1]区间最少染色次数加上当前是否染色。则完成了[0,i-1]到[0,i]区间最优解的转移。

01背包

第15周任务-01背包
时间限制：1秒 内存限制：128兆
26 次提交 5 次通过
题目描述
背包最大允许装载为C, 有n个物品要放进背包，每个物品的重量为w[1],w[2],...w[n],每个物品的价值为v[1],v[2],...v
[n], 请选择物品装进背包，使得价值最大。C为整数。
输入
第一行为物体个数n,以及背包容量C；
第二行为n个重量（实数），空格隔开
第三行为n个价值（实数），空格隔开
输出
第一行为最大装载的总价值
第二行为每个物品是否装载，1表示装，0表示不装，中间用空格隔开
(测试数据能保证最优解唯一)
样例输入
5 10
2 2 6 5 4
6 3 5 4 6
样例输出
15
1 1 0 0 1
0-1背包是动态规划问题非常经典的一个入门题，可以从多个方面来理解0-1背包推导过程。这里我用递归到递推两种形式来给出0-1背包问题解决方法。

1、递归解法：
递归的方法较为直观，可以很直观的看出状态转移的思路。但是可能递归的中间过程比较难以想象。但是递归的思维方式比较简单，只需要抓住两点：递归终点和递归方程。终点就是在递归的边界情况的返回值，递归方程即从当前节点继续搜索子问题的最优解。注意结合这里递归方程理解dp中的状态转移方程。
- 很明显这种方式无法记录我们最后选择了那些物品，而且在递归的过程中存在很多不必要的搜索，所以我们需要用到记忆化搜索来剪枝并且记录节点的选择。

2、递推解法
递推的方法其实也就是我们用到的双重循环，实际上我们可以把循环递推看成递归的一个逆过程。递归是当前不知道当前最优解，一直往子问题搜索，直到递归到子问题的边界然后开始回退，依次求出路径中的最优解。而递推则是通过已知的最优解通过状态转移方程逐步递推下一步的最优解，和贪心思想相似，只不过这里的最优解是动态的可修改的。我看见大家都是写的二维数组，这里我提供一个一维数组的方法。