动态规划-奇怪的打印机

题目描述

分析

dp[i][j] 表示打印字符串第i位到第j位所需的最少打印次数。而且可以保证的是，打印这个子串时，最优先打印的一定是s[i]这个字符（可能不是唯一方案，但一定是最优方案之一）这点比较难理解。设每次打印的起始位置为start[i]，可以证明的是必然存在最优方案（打印次数为k)，对任意i,j满足1<=i<j<=k，同时满足start[i]<start[j]。可以自己举几个例子就明白了。
当理解上面这点之后，思路就比较清晰了。dp[i][k-1]和dp[k][j]都是最优方案，此时如果s[i]==s[k]，就说明打印[i,k-1]子串和[k,j]子串时的第一步是相同的，因此打印[i,j]子串的方案可能为先打印s[i]字符，再分别按照dp[i][k-1]和dp[k][j]的方案打印上面几层字符。

题解

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

int main()
{
    string s;
    cin >> s;
    int l = s.length();
    vector<vector<int>> dp(l, vector<int>(l));
    for (int i = 0; i < l;i++)
        dp[i][i] = 1;
    for (int len = 2; len <= l;len++)
    {
        for (int i = 0; i <= l - len;i++)
        {
            int j = i + len - 1;
            dp[i][j] = dp[i + 1][j] + 1;
            for (int k = i + 1; k <= j;k++){
                if (s[i] == s[k])
    // 关键的状态转移方程
                    dp[i][j] = min(dp[i][j], dp[i][k - 1] + dp[k][j] - 1);
            }
        }
    }
    cout << dp[0][l - 1];
}