DP的简单优化

对于一个DP题，有可能不是简单的进行二维DP找出答案

首先需要写出大概的模板，推导出DP状态转移方程，再根据DP状态转移方程去优化

2023蓝桥杯 省赛B组的E题

一眼直接判定为非DP

首先写出简单的思路，有些类似最长连续子序列，然后进行线性DP，确定要求的属性为最大值，那么就是取其max值，并且进行对应的DP状态转移,$dp[j]= max(dp[i] + 1,dp[j])$需要注意的是，当$dp[i]=0$的时候，需要给$dp[j]$再加一

给出转移代码，选择将每个数字进行字符串的存储，方便取到第一位和最后一位数字

if(f[i][f[i].size() - 1] == f[j][0])
{
    if(dp[i]) dp[j] = max(dp[j],dp[i] + 1);
    else dp[j] = max(dp[j],dp[i] + 2);
}

但是这样的爆搜进行DP的方式肯定是不行的，所以需要进行优化

通过观察第一个状态转移方程来看，我们只需要关注的值只有一个数字的开头和结尾，并且在爆搜的过程中，进行了很多的重复动作

例如，当我们在后面爆搜的时候，其实已经取到了最大值，但是进行了多次搜索，所以此时来思考如何来优化掉多余的部分

其实只需要一次搜索即可完成对其最大值的选择，因为如果前面已经选择出当前位置的最大值，且$a_i$只需要去关注一下它的最开始的数字和最后的数字,下面给出优化后的DP状态转移方程。

dp[r] = max(dp[r], dp[l] + 1);

给出无优化的DP解法

for(int i = 1;i <= n;i ++) cin >> f[i];

for(int i = 1;i <= n;i ++)
{
    for(int j = i + 1;j <= n;j ++)
    {
        if(f[i][f[i].size() - 1] == f[j][0])
        {
            if(dp[i]) dp[j] = max(dp[j],dp[i] + 1);
            else dp[j] = max(dp[j],dp[i] + 2);
        }
    }
}

int ans = 0;

for(int i = 1;i <= n;i ++)
{
    ans = max(ans,dp[i]);
}
if(!ans) cout << n - 1 << '\n';
else cout << n - ans << '\n';

给出优化后的DP解法

for(int i = 1;i <= n;i ++)
{
    string s;cin >> s;
    int l = s[0] - '0', r = s[s.size() - 1] - '0';
    dp[r] = max(dp[r], dp[l] + 1);
}


int ans = 0;

for(int i = 1;i <= 9;i ++)
{
    ans = max(ans,dp[i]);
}
if(!ans) cout << n - 1 << '\n';
else cout << n - ans << '\n';