【c/c++】动态规划_动态规划算法c++代码

目录

题目一：数字三角形

输入描述

输出描述

输入输出样例

输出

代码如下：

题目二：砝码称重

问题描述

输入格式

输出格式

样例输入

样例输出

方法一：使用dfs方法

方法二：动态规划

方法三：bitset方法

题目三：回路计数

---

该篇文章用题目的形式来进行理解动态规划

题目一：数字三角形

 
    7
   3 8
  8 1 0
 2 7 4 4
4 5 2 6 5

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和（路径上的每一步只可沿左斜线向下或右斜线向下走）。

输入描述

输入的第一行包含一个整数N (1≤N≤100)，表示三角形的行数。

下面的N行给出数字三角形。数字三角形上的数都是0至 99 之间的整数。

输出描述

输出一个整数，表示答案。

输入输出样例

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出

30

讲解：第 i 行每个数的大小只与第 i-1 中的数有关

第 i 行中第 j 列的最大值与第 i-1 中第 j 列和第 j-1 列的值有关

即可列出动态表达式：arr[i][j]=max(arr[i-1][j],arr[i-1][j-1]);

最后求出最后一行中的最大值即可

代码如下：

#include<bits/stdc++.h>
using namespace std;
int main(void){
	int n;
	cin>>n;
	int arr[n][n];
	for(int i=0;i<n;i++){
		for(int j=0;j<=i;j++){
			cin>>arr[i][j];
		}
	}
	for(int i=1;i<n;i++){
		for(int j=0;j<=i;j++){
			if(j==0){//第一列最大值只与上一行的第一列有关
				arr[i][j]+=arr[i-1][j];
			}else if(j==i){//最后一列的最大值只与上一行的最后一列有关
				arr[i][j]+=arr[i-1][j-1];
			}else{
				arr[i][j]+=max(arr[i-1][j],arr[i-1][j-1]);
			}
		}
	}
	int ans=0;
	for(int i=0;i<n;i++){//找出最大值
		ans=max(arr[n-1][i],ans);
	}
	cout<<ans;
	return 0;
}

题目二：砝码称重

问题描述

你有一架天平和N个砝码，这N个砝码重量依次是W1,W2,.....,Wn。

请你计算一共可以称出多少种不同的重量？ 注意砝码可以放在天平两边。

输入格式

输入的第一行包含一个整数N.

第二行包含 N个整数：W1​,W2​,W3​,⋅⋅⋅,WN​。

输出格式

输出一个整数代表答案。

样例输入

3
1 4 6

样例输出

10

能称出的 10 种重量是：

1、2、3、4、5、6、7、9、10、11​。

1=1；

2=6−4(天平一边放 6，另一边放 4)；​

3=4−1；

4=4；

5=6−1；

6=6；

7=1+6；

9=4+6−1；

10=4+6；

11=1+4+6。

方法一：使用dfs方法

解释：砝码可以放左边、右边、也可以不放

代码如下：

#include<bits/stdc++.h>//方法一：dfs 
using namespace std;
long long arr[105];
vector <int> ans;
int n;
int ans1;
void dfs(int sum,int k){//sum是砝码能称的重量，k表示第几个砝码
	if(n==k){
		for(vector <int>::iterator it=ans.begin();it!=ans.end();it++){
			if(*it==sum||sum<=0){				
				return ;
			}
		}
		ans.push_back(sum);
		ans1++;
		return ;
	}
	
	dfs(sum+arr[k],k+1);
	dfs(sum-arr[k],k+1);
	dfs(sum,k+1);
}
int main(void){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
	ans1=0;
	dfs(0,0);//初始值都为零
	cout<<ans1;
	return 0;
}

dfs暴力在比赛中会超时只能过一部分，但是在没有思路的情况下dfs是一种很好的方法

方法二：动态规划

在dfs看完之后对该题目有了一个大概的理解，对下面了解动态规划有帮助。

说明：首先我们先考虑放一边的情况，

砝码只能放或者不放

在考虑另外一边

砝码也是只能放或者不放

我们用一个数组 arr 来用来存放某个重量是否可以被称出来，下标表示重量，数值为1表示可以称出来，数值为零表示不可以称出来。

如果为i的重量可以被称出来，那么i+w[i] (w[i]第i个砝码的重量) 也就可以被称出来

于是有动态规划表达式：

arr[j]=max(arr[j],arr[j-w[i]]);

arr[j]=max(arr[j],arr[j+w[i]]);

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void){
	ll arr[10005]={0};
	int w[105];
	int n;cin>>n;
	for(int i=0;i<n;i++){
		cin>>w[i];
	}
	arr[0]=1; //arr[0]=1的目的是什么呢？ 答:防止一个砝码出现两次的情况
	for(int i=0;i<n;i++){//向右边放砝码 ，左边物品重量 ，要达到实际平衡； 
		for(int j=10000;j>=w[i];j--){//j表示要实现的重量 
			arr[j]=max(arr[j],arr[j-w[i]]);//表示 向左边方砝码或者不放砝码
		}
	}
	for(int i=0;i<n;i++){//向左边放砝码 ，假如右边有就相当于抵消，没有就相当于放了一个砝码 
		ll Max=10000-w[i];
		for(int j=0;j<=Max;j++){
			arr[j]=max(arr[j],arr[j+w[i]]);//表示 向左边放砝码 
		}
	}int ans=0;
	for(int i=1;i<10000;i++){
		ans+=arr[i];
	}
	cout<<ans;
	return 0;
}

方法三：bitset方法

作为了解即可：

虽然用动态规划的方法在比赛中可以通过所有的数据，但是这种方法可以极大的降低时间复杂度，而且代码简洁。

#include<bits/stdc++.h>//bitset方法 
using namespace std;
const int N=1e5+5;
bitset <N> ans;//bitset方法定义 
int main(void){
	ans[0]=1;//让第一个二进制数为1 
	int n;cin>>n;int w[n];	
	for(int i=0;i<n;i++){
		cin>>w[i];
	}
	for(int i=0;i<n;i++){//位运算：向右移后w[i]位后在进行按位或(只有都为假才为假) 
		ans|=ans<<w[i];
	}
	for(int i=0;i<n;i++){
		ans|=ans>>w[i];
	}
	cout<<ans.count()-1;//求ans中1的个数。 
	return 0;
}

bitset相当于一个二进制的数组，并且可以直接用01串赋值

例如bitse t<5> S;表示定义了5个0，1数组，初始值都为零，可以进行位运算

题目三：回路计数

蓝桥学院由 21栋教学楼组成，教学楼编号1到21。对于两栋教学楼a和b，当a和b互质时，a和b之间有一条走廊相连，两个方向皆可通行，否则没有直接连接的走廊。

小蓝现在在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第一栋教学楼（即走一条哈密尔顿回路），请问他有多少种不同的访问方案？

两个访问方案不同是指存在某个i，小蓝在两个两个访问方法中访问完教学楼i后访问了不同的教学楼。（填空题）

#include<bits/stdc++.h>
using namespace std;
long long dp[1<<22][22];
int main(void){
	int g[22][22]={0,0};//用来存两栋楼是否可以连通
	for(int i=1;i<22;i++){
		for(int j=1;j<22;j++){
			if(__gcd(i,j)==1){//判断两个数是否互为质数
				g[i-1][j-1]=g[j-1][i-1]=1;//i能走到j,j也能走到i；
			}
		}
	}
	long long n=1<<21;//位运算
	dp[1][0]=1;
	for(long long i=1;i<n;i++){//列出所有可能的条件
		for(int j=0;j<21;j++){//j表示现在所在的教学楼
			if(!(i>>j&1)) continue;//判断教学楼j是否在该条件i中，不存在跳过
			for(int k=0;k<21;k++){//k表示要走的下一个教学楼
				if(!g[j][k]||(i>>k&1)) continue;//判断是否可以走到教学楼k
				dp[i+(1<<k)][k]+=dp[i][j];
			}
		}
	}
	long long ans=0;//注意用long long
	for(int i=0;i<21;i++){
		ans+=dp[n-1][i];
	}
	cout<<ans;
	return 0;
}

 关于位运算：<< 向左移，>> 向右移。例子1<<4表示1向左移4位后为：10000(二进制)。

关于第九行中g[i-1][j-1]为什么要减一；答：为了与代码16行和18行中j和k是从0开始到20一致。

关于递归表达式：

因为走到第i个教学楼，一定是从前一个教学楼走过来的，这就要满足两个条件：两个教学楼互质和第i个教学楼是没有去过的。

那么可以推出递归表达式：dp[i+(1<<k)][k]+=dp[i][j];

自认为本篇文章的难度还是比较大的，如果想要了解但是看不懂可以发评论也可以私聊，我看到了就会解答。