【校隊排位賽#2 D】 動态規劃DP

題意：有三種狀态分别是休息，做事件A，做事件B，兩種事件不能在同一天做，問怎麼安排可以讓休息的天數最少。每天可以做的事情可能是能做所有事情或者隻能做一個或者隻能休息

動态規劃思路：

其實這道題的狀态轉移的影子很明顯，目前如果可以做事情，那麼目前的最優解一定是前面異于目前選擇的最優解的最小值。

比如目前做事件A，那麼最優解就是前一天做事件B的最優解和休息的最優解的最小值。即

dp[i][1]=min(dp[i-1][0],dp[i-1][2])。

對于其他狀态也是一個道理。

最後答案就是在最後一天的三個狀态裡面挑最小就行了。

其實這個題和力扣上面這個題目是一個模子，看到我這篇部落格的人有興趣可以做一下。

#include <iostream>
#include <vector>
#include <cstdio>
#include <map>
#include <climits>
#include <string>
#include <cmath>
#include <cstring>
#include <algorithm>
#define maxn 105
using namespace std;
typedef  long long ll;
static int inf = 0x3f3f3f3f;
int main()
{
    int n;
    cin>>n;
    int a[105];
    for(int i=1; i<=n; i++)
        cin>>a[i];
    vector<vector<int>>  dp(105,vector<int>(3,inf));
    dp[0][0]=0;
    dp[0][1]=0;
    dp[0][2]=0;//能做的事情無非三種
    for(int i=1; i<=n; i++)
    {
        if(a[i]==0)      //目前狀态隻能為0時，找出前面做0、做1，做2的最優解
        {
            dp[i][0]=min(dp[i-1][0],min(dp[i-1][1],dp[i-1][2]))+1;
        }
        if(a[i]==1)  //目前狀态可以選擇0或2時，找出對應之前的最優解
        {
            dp[i][0]=min(dp[i-1][0],min(dp[i-1][1],dp[i-1][2]))+1;  //目前
            dp[i][2]=min(dp[i-1][0],dp[i-1][1]);  
        }
        if(a[i]==2)
        {
            dp[i][0]=min(dp[i-1][0],min(dp[i-1][1],dp[i-1][2]))+1;
            dp[i][1]=min(dp[i-1][0],dp[i-1][2]);

        }
        if(a[i]==3)
        {
            dp[i][0]=min(dp[i-1][0],min(dp[i-1][1],dp[i-1][2]))+1;
            dp[i][2]=min(dp[i-1][0],dp[i-1][1]);
            dp[i][1]=min(dp[i-1][0],dp[i-1][2]);
        }
    }
    int minone=inf;
    for(int i=0;i<=3;i++)//最後一天在三種狀态裡面挑最小
    minone=min(minone,dp[n][i]);
    cout<<minone<<endl;
    return 0;
}