leetcode lcp19

秋叶收藏集

动态规划。我们用 dpi 来表示从第 0 片树叶到第 i 片树叶（[0, i]），并且第 i 片树叶处于状态 j 的时候总共需要的最小操作次数。

j 分为0、1、2三种状态，0 表示黄色前面的红色，1 表示中间的黄色，2 表示黄色后面的红色。

要注意，题目说了每一种状态包含的叶子数量必须至少为 1，所以叶子的数量必须==大于等于==状态的数量。所以当 i 等于 0 时，j 必须等于 0；当 i 等于 1 时，j 只能等与 0 或 1；当 i 大于等于 2 时，j 可以等于 0 或 1 或 2。

注意到实际上dp是从3号状态开始更新，可以优化为3个变量进行储存

class Solution{
public:
    int dp[4];
    int minimumOperations(string leaves){
        int Length=leaves.length();
        dp[1]=(leaves[0]=='y');dp[2]=dp[3]=0x3fffff;
        for (int i=1;i<Length;i++){
            dp[3]=min(dp[2],dp[3])+(leaves[i]=='y');
            dp[2]=min(dp[1],dp[2])+(leaves[i]=='r');
            dp[1]=dp[1]+(leaves[i]=='y');
        }
    return dp[3];
    }
};