动态规划(算法篇)

算法之动态规划

动态规划(dp)

概念：

• 将递归算法重新写成非递归算法，让后者把那些子标题的答案体系地记载在一个表(dp数组)内，这种方法叫做动态规划
  
• 通常用于求解具有最优性子的标题(最优子结构&最优子标题)，盼望找到具有最优值的解。
  
• 焦点为穷举，动态规划标题通常具有最优子结构，重叠子标题和状态转移方程的特性。
  

根本头脑：

• 实用于子标题不是独立的情况，也就是各子标题包罗公共的子标题，鉴于会重复的求解各个子标题，对每个标题只求一遍，将其生存在一张表中，从而克制重复盘算。
  

特性：

• 最优子结构：当标题的最优解包罗了其子标题的最优解时，称该标题具有最优子结构性子。
  
• 重叠子标题：在用递归算法自顶向下解标题时，每次产生的子标题并不总是新标题，有些子标题被反复盘算多次。动态规划算法使用这个子标题重叠性子，对每一个标题只解一次，而后将其解生存在一个表格(dp数组)中，在以后尽大概多地使用这些子标题的解。
  
• 状态转移方程(最关键)：
  
  
  
  • 是动态规划中本阶段的状态通常是上一阶段状态和上一阶段决定的效果。假如给定了第K阶段的状态Sk以及决定uk(Sk)，则第K+1阶段的状态Sk+1也就完全确定
    
  • 也就是递推方程，一个状态的解通常可以由前一个状态的解得出
    
  • 状态是由本身界说的通常可以以为是函数参数，dp数组的索引。
    
  • 状态转移就是从一个状态酿成另一个状态，就比方本质为斐波那契数列的爬楼梯标题，从N-1阶或N-2的楼梯上到N阶的楼梯就称为状态转移.
    
  • 状态压缩：偶然间并不必要生存全部状态，当生存的状态镌汰，导致算法的空间复杂度低落的本事叫做状态压缩
    
  
  

能办理的标题：

• 计数
  
• 最值
  
• 存在性(是和否的标题，比方01背包)
  

解题步调：

• 明确状态：也就是原标题和子标题中会厘革的变量,状态的种数决定dp数组的维度。根据题意界说状态，这个状态大概是求解标题会厘革的量，由于动态规划本质就是穷举，以是这个状态应该是穷举全部方案可以或许找到求解的目的
  
• 明确选择：也就是导致状态产生厘革的举动。选择就是限定，当我们必要求解标题时，就必要不停地更新选择限定中的数据，来不停地产生多个方案，从而从中找到最优方案。
  
• 明确dp函数/数组的界说：就是求解的标题的函数，这个函数要求什么
  
• base case：初始状态，根据题意找到初始状态，然后写出状态转移方程然后写出自顶向下大概自底向上递推的解法
  

分析标题：

• 先分析标题，用备忘录消除重叠子标题，写出自顶向下解法
  
• 进一步，可以写出自底向上解法
  
• 再进一步，大概可以优化空间复杂度
  

动态规划框架：

1. //初始化 base case
2. dp[0][0][...]=base;
3. //进行状态转移
4. for 状态1 in 状态1的所有取值：
5.     for 状态2 in 状态2的所有取值：
6.         for ...
7.             dp[状态1][状态2][...]=求最值(选择1，选择2，...);

复制代码

例子：
零钱兑换标题：
分析标题：

• 设F(n)为求解凑出目的金额为n的最少硬币数，通太过析标题，求解目的金额为n的最小硬币数F(n)=min(F(n-coin1),F(n-coin2)…)，当coins=[1,2,5]，目的金额为11时，则F(11)=min(F(11-1)，F(11-2),F(11-5))，然后依次递推下去，如许就形成了自顶向下的求法，但是会有重复盘算，因此必要使用备忘录也就是影象性递归来剪枝举行优化
  

• 自顶向下解法：
  

1. class Solution {
2.     //因为这是自顶向下递推，初始化则只需要初始化为达不到的值就行了
3.     vector<int>v;
4.     int dp(vector<int> coins,int amount){
5.         if(amount==0) return 0;
6.         if(amount<0) return -1;
7.         if(v[amount]!=-2) return v[amount];
8.         int res=INT_MAX;
9.         for(int coin:coins){
10.             int sub=dp(coins,amount-coin);
11.             if(sub==-1) continue;
12.             res=min(res,sub+1);
13.         }
14.         //存到备忘录中
15.         v[amount]=(res==INT_MAX)?-1:res;
16.         return v[amount];
17.     }
18. public:
19.     int coinChange(vector<int>& coins, int amount) {
20.         v.assign(amount+1,-2);
21.         return dp(coins,amount);
22.     }
23. };

复制代码

• 自底向上解法：
  

1. class Solution {
2. public:
3.     //状态：目标金额 amount 因为每选择一枚硬币就会导致amount数值减少
4.     //选择：coins数组，包含着硬币面额，选择不同面额的硬币就会导致amount的不同，凑出amount的方案也不同
5.     //函数定义：coinChange函数，对于目标金额amount，至少需要coinChange(coins,amount)枚硬币
6.     //base case：当amount=0时，则最少需要0个硬币，当amount<0，则无法凑出目标金额
8.     int coinChange(vector<int>& coins, int amount) {
9.         //目标金额所用最多硬币数为amount，因为是求解最小硬币数问题,所以应该初始化比amount还大
10.         vector<int>dp(amount+1,amount+1);
11.         //base case
12.         dp[0]=0;
13.         //枚举所有状态
14.         for(int i=0;i<amount+1;i++){
15.             for(int j:coins){
16.                 //判断当前amount是否小于选择的面额，如果小于就跳过
17.                 if(i-j<0) continue;
18.                 //状态转移，求出凑出当前面额i的最小硬币数
19.                 dp[i]=min(dp[i],dp[i-j]+1);
20.             }
21.         }
22.         return (dp[amount]>=amount+1)?-1:dp[amount];
23.     }
24. };

复制代码

01背包标题

• 经典的动态规划标题，01背包的01就对应着我是否将当前物品放入背包中，由题意可知，我们只必要求解dp[N] [W]就可以得到答案，分析标题对于选择i物品时，当前背包剩余重量为w时，我们将物品i放入背包则dp [w]=dp[i-1] [w-wt[i-1]]+val[i-1]，我们不将物品i放入背包则dp [w]=dp[i-1] [w]，因此我们取其最大值就可以求出对于前i个物品，当背包涵量为w时，可以装的最大代价，因此状态转移方程为max(dp[i-1] [w],dp[i-1] [w-wt[i-1]]+val[i-1]);
  

1. #include <iostream>
2. using namespace std;
4. //状态：背包的空余容量剩多少，可选择的物品还有哪些
5. //选择：把这个物品是否放进背包
6. //dp[i][w]定义，对于前i个物品，当背包的容量为w时，可以装的最大价值是dp[i][w]
7. //base case:dp[0][...]=dp[...][0]=0,因为当选择物品为0的时候无论w多少都为0，当背包容量为0时，无论物品多少都无法放进
8. int main(){
9.     int N,W;
10.     cin>>N>>W;
11.     int val[N],wt[N];
12.     for(int i=0;i<N;i++){
13.         cin>>val[N]>>wt[N];
14.     }
15.     int dp[N+1][W+1];
16.     memset(dp,0, sizeof(int)*((N+1)*(W+1)));
17.     for(int i=1;i<=N;i++){
18.         for(int w=W;w>=wt[i-1];w--){
19.             dp[i][w]=max(dp[i-1][w],dp[i-1][w-wt[i-1]]+val[i-1]);
20.         }
21.     }
22.     cout<<dp[N][W];
23.     return 0;
24. }

复制代码

完全背包标题：
有 N 种物品和一个容量是 V 的背包，每种物品都有无穷件可用。
第 i 种物品的体积是 vi，代价是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不高出背包涵量，且总代价最大。
输出最大代价。
二维dp:

1. #include <bits/stdc++.h>
2. using namespace std;
4. const int N=1e3+1;
5. int n,m;
6. int v[N],w[N],dp[N][N];
8. int main(){
9.     cin>>n>>m;
10.     for(int i=1;i<=n;++i) cin>>v[i]>>w[i];
11.     for(int i=1;i<=n;++i){
12.         for(int j=0;j<=m;++j){
13.             dp[i][j]=dp[i-1][j];
14.             if(j-v[i]>=0) dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
15.         }
16.     }
17.     cout<<dp[n][m]<<endl;
18.     return 0;
19. }

复制代码

状态压缩：

1. #include <bits/stdc++.h>
2. using namespace std;
4. const int N=1e3+1;
5. int n,m;
6. int v[N],w[N],dp[N];
8. int main(){
9.     cin>>n>>m;
10.     for(int i=1;i<=n;++i) cin>>v[i]>>w[i];
11.     for(int i=1;i<=n;++i){
12.         for(int j=v[i];j<=m;++j){
13.             dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
14.         }
15.     }
16.     cout<<dp[m]<<endl;
17.     return 0;
18. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金