这个难度直接可以用dp去解决我们看
那么我们用代码表示这个字符的个数，那么从上就得出
可以看出从我们都可以直接从前一个继承过来，和我们单独去操作即可
所以我们遍历每一步然后对于每一步将字符串里的操作就行，我们只需要知道数量，并不需要知道具体位置。
所以时间复杂度就是
讯享网
首先知道初级难度的用dp去维护，我们这里也是先去找子问题，看看能不能拆解出子问题：
假设经过过一次，之后变成和。问题就变成了计算替换(t-1)次的长度，加上，替换(t-1)次的长度。
那么我们还用表示字母替换次的长度
上面说的例子：
那么我们做推广一下：
设
$$ dp[i][j]=sum^{j+c}_{k=j+1}dp[i-1][k%26] $$
是为了这个阶段
初始状态：
最终结果$$sum_{j=0}^{25}dp[t][j] imes a[j]$$其中是中字母的出现次数
这个复杂度就是解决第一题的复杂度
如果就是第一题的要求，都只产生一个，产生两个。
$\( dp[i][0]=dp[i-1][1] \)\(</p> <p>\)\( dp[i][1]=dp[i-1][2] \)\(</p> <p>\)\( dp[i][25]=dp[i-1][0]+dp[i-1][1] \)\(</p> <p>用矩阵乘法表示：<br>\)\( left[begin{array}{c} dp[i][0] \ dp[i][1] \ dp[i][2] \ vdots \ dp[i][23] \ dp[i][24] \ dp[i][25] end{array} ight]=left[begin{array}{ccccccc} 0 & 1 & 0 & 0 & cdots & 0 & 0 \ 0 & 0 & 1 & 0 & cdots & 0 & 0 \ 0 & 0 & 0 & 1 & cdots & 0 & 0 \ vdots & vdots & vdots & vdots & ddots & vdots & vdots \ 0 & 0 & 0 & 0 & cdots & 1 & 0 \ 0 & 0 & 0 & 0 & cdots & 0 & 1 \ 1 & 1 & 0 & 0 & cdots & 0 & 0 end{array} ight]left[begin{array}{c} dp[i-1][0] \ dp[i-1][1] \ dp[i-1][2] \ vdots \ dp[i-1][23] \ dp[i-1][24] \ dp[i-1][25] end{array} ight] \)\(<br>把上式中的三个矩阵记作<br>\)\( A[i]=M imes A[i-1] \)\(<br>那么就有<br>\)\( begin{align} A[t] &= M imes A[i-1] \ &= M imes M imes A[i-2] \ & ...\ &=M^t imes A[0] end{align} \)\(<br>其中\)M^t\( 可以用矩阵快速幂计算。\)A[0]$是长为26的列向量，值全为1，对应着
讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/202414.html