3389.Minimum-Operations-to-Make-Character-Frequencies-Equal

此题的突破口是对所有可能的频率进行尝试，暴力地从1枚举到max_freq（对应出现频次最多的字母），然后考察是否有一种方法能够将所有字符的频次都变换成target。

对于题目中的规则，我们最需要深刻体会的就是第三条。事实上，我们不会将某个字符连续变换两次。比如说，a->b->c，那这两次变换，还不如直接删除a，添加c来得直观。所以唯一使用规则三的情景就是：对于字母表相邻的两种字符x和y，如果x需要删除一些，y需要增加一些，那么我们不妨将部分的x转化为y，以节省操作。更具体的，如果x需要删除a个，y需要增加b个，普通的“删除+增加”的操作需要a+b次，但是如果将c=min(a,b)个x转化为y次，我们就额外节省了c次操作。

此题的复杂之处在于，即使我们确定了某个目标频次target，但规则同时也允许部分字符的频次变成零。对于这两个不同的“做法”，需要考虑的策略其实也是不同的。因此我们对于a->z的的每个字符，都要考虑到它的两种“做法”。

假设我们考虑相邻的两个字符i-1和字符i。令diff[i]=freq[i]-target，正则表示相比于target多了，负表示相比于target还亏欠。定义dp[i][0]表示对字符i采取清零操作的总最小代价；dp[i][1]表示对字符i变换成target频次的总最小代价。

1. 如果对字符i采取清零，即dp[i][0]，那么所需要的操作数必然是freq[i]，与之前的状态无关。故dp[i][0] = min(dp[i-1][0], dp[i-1][1]) + freq[i];

2. 如果对字符i变换成目标targt，那么我们分两种情况：

   • 不采用规则3，只靠增删，那么同理有dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + abs(diff[i])
   • 采用规则3，同时前一个字符的操作是通过删减达到清零，这就意味着a=freq[i-1]，b=abs(diff[i])，故c=min(a,b)，且有dp[i][1] = dp[i-1][0]+abs(diff[i])-c
   • 采用规则3，同时前一个字符的操作是通过删减达到target，这就意味着a=diff[i-1]，b=abs(diff[i])，故c=min(a,b)，且有dp[i][1] = dp[i-1][0]+abs(diff[i])-c

最终对于target而言，最优解就是遍历完26个字母后的min(dp[25][0],dp[25][1])

全局最取遍历所有target之后的最优解。