本文共 1816 字，大约阅读时间需要 6 分钟。

题意：一个长度为n(<=100)的数组a(1<=ai<=100)，ai表示参加活动 i 的时候需要穿的衣服类型，每次参加活动时可以选择穿上ai或者脱到ai为止（脱掉的这一件就不能穿了，下次需要这种就需要新穿一件），问参加完所有活动最少穿几次衣服。

题解：dp[i][j]表示参加活动 i~j 穿的衣服的最少次数。最开始全部初始化为INF，然后慢慢考虑脱。

• 每次在dp[i][i~j-1]的基础上更新dp[i][j]。只有当a[k:i~j-1]==a[j]存在而且留到参加活动 j 的时候才-1，否则就等于dp[i][k]+dp[k-1][j]-1。
• 判断存在a[k:i~j-1]==a[j]时才有可能-1，能留到才能-1。（所以说为什莫不-2，-3？？？）
• 尽力理解了，先拉拉进度，毕竟还是小白，不一定一下子就能完全理解

代码：

#include 
   
    // #define int long longusing namespace std;const int N = 1e2 + 10;const int INF = 1e9;int n, a[N], dp[N][N];signed main() {    int T;    cin >> T;    for (int _ = 1; _ <= T; _++) {        cin >> n;        int len, i, j, k;        for (i = 1; i <= n; i++)            for (j = 1; j <= n; j++) dp[i][j] = INF;  //先全穿，然后再考虑脱        //以下操作，我们首先认为dp[i][j]就是区间i,j的最小次数。那么为什莫这么转移是正确的呢？        //为什莫只考虑k,j因为i~k，k+1~j中间该脱的都已经脱了        // emmm，其实还是没有思考透彻，它并不是一次转移就能成功的        //不对，应该这样思考：i~j-1该脱的都已经脱了，现在我们考虑的知识加入j的时候是否需要多穿那一件        //....emmm所以还是大佬们的题解写得太复杂了，之许哟啊判断是否存在k即可        //也不对，万一遇到k，但是到j-1的时候已经脱到了呢，原来这才是每次a[k]==a[j]都需要判断更新的原因        // dp[i][k]就表示没脱掉k，dp[k-1][j]表示没脱掉k的最小次数，得两方面考虑崩不崩得住        for (i = 1; i <= n; i++) scanf("%d", &a[i]), dp[i][i] = 1;        for (len = 2; len <= n; len++) {            for (i = 1; i + len - 1 <= n; i++) {                j = i + len - 1;                for (k = i; k < j; k++) {                    if (a[k] == a[j])                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] - 1);                    // 例：3 2 1 1 2 3                    else                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);                }                // bool f = true;                // for (k = i; k < j; k++)                // if (a[k] == a[j]) f = false;                // dp[i][j] = dp[i][j - 1] + f;            }        }        printf("Case %d: %d\n", _, dp[1][n]);    }    return 0;}
   

转载地址：https://blog.csdn.net/I_have_a_world/article/details/117636253 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！