【简单DP】房屋染色

题意：

N 个房子在一列直线上，现在需要给所有房子染色，颜色有红色、蓝色和绿色三种，染色费用和房子与颜色都有关。
若相邻的房屋颜色不能相同，那么所有可行的染色方案中费用最小的方案的费用是多少？

思路：

首先，状态设计：状态设计的本质上是将问题的所有dfs状态进行分类，将这一类的所有状态中找到一个最优解，在这些最优解之间转移（最优子结构）

在状态设计时注意状态机原则：在给所有dfs状态分类时做到不重不漏，且dp状态是确定的

设计阶段的时候按照字面意思去设计阶段，别硬按照线性去设计啊QwQ

怎么按字面理解，其实就是去心里模拟一下过程，看看子问题就好了

在此题中，若只根据位置i分类，状态时模糊不清的，因此再加一个描述：颜色。因此，位置和房子颜色决定了我们的dp状态

考虑是否要多加一维，可以想想这一维是否影响接下来的决策，或者想想是什么影响了该dp数组的贡献

这一维，加的应该是该阶段的参数，这样更好转移

这个参数可以是该阶段的决策

因此我们可以遍历决策，考虑是什么影响了决策

设dp[i][j]为所有位置为i，房子颜色为j的所有dfs状态中，费用最少的状态

一般属性就为数/最值，数的话初始化为0，最值的话初始化为inf或mnf

属性是最值，因此应该初始化为mnf

还有就是，考虑统计答案需要什么参数，如果需要的话就加上

上述是比较暴力的DP，如果暴力DP爆了空间的话，那就考虑滚动数组，爆了时间的话，去重新设计状态，根据转移的特殊性去优化状态设计，或者直接根据题目给的参数去设计（玄学，状态一定要多试），还有根据记录答案需要什么值就多一个维度

然后去考虑状态转移：

考虑状态转移时本质上是枚举上一个状态是什么，我们可以枚举决策，或者直接枚举上一个状态也行

枚举的时候，不论是枚举决策还是去枚举上一层的状态，一定要包含所有情况，这样才能保证DP的正确性！！

当状态转移发现转移不了或者转移地好几把怪的时候，就得考虑重新设计DP状态了

在考虑状态转移时，先考虑决策（入边），先给决策分分类，然后对于每一个决策，再对可能的父结点分类，注意在状态转移的过程中每种状态要做到不重不漏

在此题的状态转移中，决策只有三条：选择涂红，还是蓝，还是绿。如果决策（入边）是红，那么父结点只能是第i-1位置图蓝色或绿色，其他颜色同理

可以发现dp状态图的转移顺序其实是拓扑序

这个顺序其实就是，先去枚举阶段，再去枚举状态，最后去枚举决策

关于初始化：

dp数组的初始化其实本质上就是给dp状态图的起点初始化，一般初始化时只初始化为0或inf或mnf

在此题中，因为第i个位置的状态只由第i-1个状态转移过来，因此还能使用滚动数组进行空间优化

对一个位置i，我们直接用dp2数组copy一下上一个位置的状态，那么dp数组就由dp2转移过来

Code：

#include 
using namespace std;
const int mxn=2e4+10;
int n;
int w[mxn][3],dp[mxn][3];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=0;j<3;j++) scanf("%d",&w[i][j]);
    }
    dp[1][0]=w[1][0];
    dp[1][1]=w[1][1];
    dp[1][2]=w[1][2];
    for(int i=2;i<=n;i++){
        dp[i][0]=min(dp[i-1][1],dp[i-1][2])+w[i][0];
        dp[i][1]=min(dp[i-1][0],dp[i-1][2])+w[i][1];
        dp[i][2]=min(dp[i-1][0],dp[i-1][1])+w[i][2];
    }
    printf("%d\n",min(dp[n][0],min(dp[n][1],dp[n][2])));
    return 0;
}

滚动数组优化：

#include 
using namespace std;
const int mxn=2e4+10;
int n;
int w[mxn][3],dp[3],dp2[3];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=0;j<3;j++) scanf("%d",&w[i][j]);
    }
    dp[0]=w[1][0];
    dp[1]=w[1][1];
    dp[2]=w[1][2];
    for(int i=2;i<=n;i++){
        memcpy(dp2,dp,sizeof(dp));
        dp[0]=min(dp2[1],dp2[2])+w[i][0];
        dp[1]=min(dp2[0],dp2[2])+w[i][1];
        dp[2]=min(dp2[0],dp2[1])+w[i][2];
    }
    printf("%d\n",min(dp[0],min(dp[1],dp[2])));
    return 0;
}

再来一题进阶版：

题意：N 个房子在一列直线上，现在需要给所有房子染色，颜色有 K 种，染色费用和房子与颜色都有关。
若相邻的房屋颜色不能相同，那么所有可行的染色方案中费用最小的方案的费用是多少？

原理是一样的，多一层枚举就好了

Code：

#include 
using namespace std;
const int mxn=2e4+10,kmxn=5e2+10,mnf=0x3f3f3f3f;
int n,K;
int dp[mxn][kmxn],w[mxn][kmxn];
int main(){
    memset(dp,mnf,sizeof(dp));
    scanf("%d%d",&n,&K);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=K;j++) scanf("%d",&w[i][j]);
    }
    for(int i=1;i<=K;i++) dp[1][i]=w[1][i];
    for(int i=2;i<=n;i++){
        for(int j=1;j<=K;j++){
            for(int k=1;k<=K;k++){
                if(j==k) continue;
                dp[i][j]=min(dp[i][j],dp[i-1][k]+w[i][j]);
            }
        }
    }
    int ans=mnf;
    for(int i=1;i<=K;i++) ans=min(ans,dp[n][i]);
    printf("%d\n",ans);
    return 0;
}

总结：

状态设计：状态设计的本质上是将问题的所有dfs状态进行分类，将这一类的所有状态中找到一个最优解，在这些最优解之间转移（最优子结构）

在状态设计时注意状态机原则：在给所有dfs状态分类时做到不重不漏，且dp状态是确定的

一般属性就为数/最值，数的话初始化为0，最值的话初始化为inf或mnf

在考虑状态转移时，先考虑决策（入边），先给决策分分类，然后对于每一个决策，再对可能的父结点分类，注意在状态转移的过程中每种状态要做到不重不漏

可以发现dp状态图的转移顺序其实是拓扑序

关于初始化：

dp数组的初始化其实本质上就是给dp状态图的起点初始化，一般初始化时只初始化为0或inf或mnf

关于滚动数组：对一个位置i，我们直接用dp2数组copy一下上一个位置的状态，那么dp数组就由dp2转移过来