C++数据结构与算法（动态规划）

- 日理万妓 2021-10-31 16:14 332阅读 0赞

> **动态规划（dynamic programming）**与分治方法相似，都是通过组合子问题的解来求解原问题。分治方法将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。与之相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。在这种情况下，分治算法会做出许多不必要的工作，它会反复求解那些公共子问题。而动态规划只对每个子子问题求解一次，将其解保存在一个表格中，从而无需每次求解一个子子问题时都要重新计算，避免了不必要的计算工作。

> 按如下步骤来设计一个动态规划算法：
> 
> 1.  刻画一个最优解的结构特征；
> 2.  递归地定义最优解的值；
> 3.  计算最优解的值，通常采用自底向上的方法；
> 4.  利用计算出的信息构造一个最优解。

# 1 案例分析 #

## 1）清雨的自助餐 ##

> 题目描述：清雨面前有n种食物，排成一排，清雨可以选择其中的若干种食物，但是不能连续选择相邻的食物，问有多少种方法？其中1<n<90。
> 
> 输入描述：
> 
> 一个整数n
> 
> 输出描述：
> 
> 一个数的答案
> 
> 输入样例：
> 
> 3
> 
> 输出样例：
> 
> 5
> 
> **解题思路：设dp\[i\]表示1~i的食物有多少种选法。考虑第i种食物，若选，则i-1不能选，所以方案为dp\[i-2\]；若不选，则方案数为dp\[i-1\]。故转移方程dp\[i\]=dp\[i-1\]+dp\[i-2\]。易得初始条件为：dp\[1\]=dp\[i-1\]+dp\[i-2\]。**
> 
> **90项用long long刚好存的下。**

#include<bits/stdc++.h>
    using namespace std; 
    
    typedef long long LL;
    const int N=90+5;
    
    int n;
    LL a[N];
    
    int main()
    {
    	scanf("%d",&n);
    	a[1]=2;
    	a[2]=3;
    	for(int i=3;i<=n;i++)
    	{
    		a[i]=a[i-1]+a[i-2];
    	}
    	printf("%lld\n",a[n]);
    	return 0;
    }

结果：

![20190817211946781.png][]

## 2）糖果 ##

> 题目描述：有一堆总数为奇数的糖果，小明和小红依次从这堆糖果中取一个糖果。首先将糖果排成一个环，然后小明先拿，之后二人只能从队尾或者队首拿糖果，直到所有糖果拿完，最后拿糖果多的获胜。
> 
> 输入描述：
> 
> 第一行：N
> 
> 第2至N+1行：每行一个数，代表糖果数。
> 
> 输出描述：
> 
> 一个数，请输出胜利者比失败者多拿多少糖果
> 
> 输入样例：
> 
> 4
> 
> 1
> 
> 55
> 
> 41
> 
> 2
> 
> 输出样例：
> 
> 54
> 
> 小明先选55，此时环从55处断开，变为序列\[41,2,1\]
> 
> 小红先选择行首的41，此时剩余的序列为\[2,1\]
> 
> 小明选择行首的2，此时剩余的序列为\[1\]
> 
> 小红选择剩余的1.
> 
> 此时小明获胜，比小红多15颗糖果。
> 
> **解题思路：带博弈的动态规划**
> 
> **设dp\[i\]\[j\]为只考虑i~j的糖果序列，先手能比后手多的糖果数，则转移方程为**
> 
> **dp\[i\]\[j\]=max(a\[i\]-dp\[i+1\]\[j\],a\[j\]-dp\[i\]\[j-1\])**
> 
> **为环的话，只需要枚举第一个取得的糖果，即可转为序列上的问题。**

//糖果问题
    #include<iostream>
    #include<vector>
    using namespace std;
    
    int predictWinner(vector<int>candies)
    {
    	int length=candies.size();
    	if(length==0) return false;
    	vector<vector<int> > dp(length,vector<int>(length,0));
    	for(int i=0;i<length;i++)
    	{
    		dp[i][i]=candies[i];
    	}
    	for(int d=1;d<length;d++)
    	{
    		for(int i=0;i<length;i++)
    		{
    			dp[i][(i+d)%length]=max(candies[i]-dp[(i+1)%length][(i+d)%length],
    			candies[(i+d)%length]-dp[i][(i+d-1)%length]);
    		}
    	}
    	int result=INT_MIN;  //INT_MIN= -2^31=-2147483648
    	for(int i=0;i<length;i++)
    	{
    		result=max(result,dp[i][(i+length-1)%length]);
    	}
    	return result;
    }
    
    int main()
    {
    	int length=0;
    	int candies[10000];
    	cin>>length;
    	for(int i=0;i<length;i++)
    	{
    		cin>>candies[i];
    	}
    	vector<int> v(candies,candies+length);
    	cout<<predictWinner(v)<<endl;
    }

结果：

![20190817211857862.png][]

[20190817211946781.png]: /images/20211031/b5394373878c4147bfbcffd8f611a3d6.png
[20190817211857862.png]: /images/20211031/d7e52cd32f614ef485eec50a783cc3fb.png