京东笔试8-27号 Q3漂亮串 朴素易懂DP
问题描述：
输入一个n
输出长度为n的，只包括小写字母的，至少包含两个‘red’字串的字符串的数量对 1e9+7 的模。
抛砖引玉一个朴素易懂的DP：
总的思路是做减法，用 所有长度为n的字符串数 减去 长度为n不含'red'的字符串数 和 长度为n有且仅有一个'red'的字符串数。
维护一个 dp[2][N] 的二维数组, 第一个下标代表字符串中'red'出现的次数，第二个下标代表字符串长度
于是dp[0][i] 即为 长度为 i 其中包含 0 个'red'的字符串个数(即不出现'red')
于是dp[1][i] 即为 长度为 i 其中包含 1 个'red'的字符串个数
最终结果就应该是很简单的 26^(N) - dp[0][N] - dp[1][N]
重头戏是状态转移防程：
首先考虑 dp[0][i], 分 第 i 位不是'd' 和 第 i 位是'd' 两种情况考虑
如果第 i 位不是'd'， 那前面 [0~i-1] 位只要不包含'red'就行，而第i位除'd'以外还有25种选择，dp[0][i-1] * 25
如果第 i 位是'd'，那其前面两位不能是're', 考虑从 dp[0][i-1] 中剔除所有的 dp[0][i-3]'re'的情况，第i位只有'd'一种选择，(dp[0][i-1] - dp[0][i-3]) * 1
因此综合来看，dp[0][i] = dp[0][i-1] * 25 + (dp[0][i-1] - dp[0][i-3]) * 1 = dp[0][i-1] * 26 - dp[0][i-3]
其次考虑 dp[1][i], 也分 第 i 位不是'd' 和 第 i 位是'd' 两种情况考虑
如果第 i 位不是'd'， 那前面 [0~i-1] 位需要包含一次'red'，而第i位除'd'以外还有25种选择，dp[1][i-1] * 25
如果第 i 位是'd'，那又有两种情况， “ 不包含'red'的[0~i-3]+‘red’ ” 或者 “ 包含'red'的[0~i-3]+非're'+'d' ”
“ 不包含'red'的[0~i-3]+‘red’ ”，非常简单，即 dp[0][i-3] * 1
“ 包含'red'的[0~i-3]+非're'+'d' ”的情况与之前类似，考虑从 dp[1][i-1] 中剔除所有的 dp[1][i-3]'re'的情况，第i位只有'd'一种选择，(dp[1][i-1] - dp[1][i-3]) * 1
因此综合来看，dp[1][i] = dp[1][i-1] * 25 + dp[0][i-3] + (dp[1][i-1] - dp[1][i-3]) * 1
整体代码如下：
#include <iostream>
#include <vector>
using namespace std;
#define MOD 1000000007
long long beautiString(int n){
long long res = 0;
vector<vector<long long>> dp(2, vector<long long>(n+1, 0));
dp[0][0] = 1; dp[0][1] = 26; dp[0][2] = 26 * 26;
dp[1][0] = 0; dp[1][1] = 0 ; dp[1][2] = 0;
res = 26 * 26;
for(int i = 3; i <= n; i++){
// 0次red: (dp[0][i-1] * 25) + (dp[0][i-1] - dp[0][i-3])
// 第i位不是d 第i位是d,前两位不能是re
// 需要从 dp[0][i-1] 把 dp[0][i-3]'re' 的情况减去
dp[0][i] = (dp[0][i-1] * 26 % MOD - dp[0][i-3]) % MOD;
// 1次red: (dp[1][i-1] * 25) + (dp[0][i-3] + (dp[1][i-1] - dp[1][i-3]))
// 第i位不是d 第i位是d,两种情况: dp[0][i-3]'red'&nbs***bsp;dp[0][i-3]非're'
// 需要从 dp[1][i-1] 把 dp[1][i-3]'re' 的情况减去
dp[1][i] = (dp[1][i-1] * 25 % MOD + dp[0][i-3] + dp[1][i-1] - dp[1][i-3]) % MOD;
res = (res * 26) % MOD;
}
res += MOD - (dp[0][n] + dp[1][n]) % MOD;
return res % MOD;
}
int main(){
int n = 100;
cout << beautiString(n);
return 0;
} 
，
查看19道真题和解析
