类01背包问题，选or不选
问题翻译：
S有多少个不同的子串与T相同
S[1:m]中的子串与T[1:n]相同的个数
由S的前m个字符组成的子串与T的前n个字符相同的个数
状态：
子状态：由S的前1,2,...,m个字符组成的子串与T的前1,2,...,n个字符相同的个数
F(i,j): S[1:i]中的子串与T[1:j]相同的个数
状态递推：
在F(i,j)处需要考虑S[i] = T[j] 和 S[i] != T[j]两种情况
当S[i] = T[j]:
1：让S[i]匹配T[j]，则 F(i,j) = F(i-1,j-1)
2：让S[i]不匹配T[j],则问题就变为S[1:i-1]中的子串与T[1:j]相同的个数，则 F(i,j) = F(i-1,j)
故，S[i] = T[j]时，F(i,j) = F(i-1,j-1) + F(i-1,j)
当S[i] != T[j]:
问题退化为S[1:i-1]中的子串与T[1:j]相同的个数
故，S[i] != T[j]时，F(i,j) = F(i-1,j)
初始化：
引入空串进行初始化
F(i,0) = 1 ---> S的子串与空串相同的个数，只有空串与空串相同
返回结果：
F(m,n)
举个栗子：
母串：“rabbbit” 子串：“rabbit”
如果子串的最后一个字母和母串的最后一个字母不同，说明新加的母串字母没有产生新的可能性，可以沿用该子串在较短母串的出现次数，所以dp(i)(j) = dp(i-1)(j)
如果子串的最后一个字母和母串的最后一个字母相同，说明新加的母串字母带来了新的可能性，我们不仅算上dp(i-1)(j)，也要算上新的可能性。那么如何计算新的可能性呢，其实就是在既没有最后这个母串字母也没有最后这个子串字母时，子串出现的次数，我们相当于为所有这些可能性都添加一个新的可能。所以，这时dp(i)(j) = dp(i-1)(j) + dp(i-1)(j-1)。
class Solution { public: int numDistinct(string S, string T) { int s_size = S.size(); int t_size = T.size(); // S的长度小于T长度，不可能含有与T相同的子串 if (S.size() < T.size()) return 0; // T为空串，只有空串与空串相同，S至少有一个子串，它为空串 if (T.empty()) return 1; // F(i,j)，初始化所有的值为0 vector<vector<int> > f(s_size + 1, vector<int>(t_size + 1, 0)); // 空串与空串相同的个数为1 f[0][0] = 1; for (int i = 1; i <= s_size; ++i) { // F(i,0)初始化 f[i][0] = 1; for (int j = 1; j <= t_size; ++j) { // S的第i个字符与T的第j个字符相同 if (S[i - 1] == T[j - 1]) { f[i][j] = f[i - 1][j] + f[i - 1][j - 1]; } else { // S的第i个字符与T的第j个字符不相同 // 从S的前i-1个字符中找子串，使子串与T的前j个字符相同 f[i][j] = f[i - 1][j]; } } } return f[s_size][t_size]; } };
变种走方格
该题类似于走迷宫，蘑菇代表不能走通，但不同的是，迷宫可以向前后左右四个方向移动，但该题走的方式只能向右或者向下两个方向移动，注意：右边界处只能向一个方向移动，因此走不通路径的概率是不相等的。比如：M = 2 N = 3
1 2 3
4 5 6
在1时：既可向右走到2，也可向下走到4，因此从1-->2 和从1-->4的概率均为0.5
在2时：即可向右走到3，也可向下走到5，因此从2-->3和从2-->5的概率均为0.5
在3时：只能走到6，因此从3-->6概率为1
在4、5、6时，只能向右走，因此4-->5和5-->6的概率均为1。
通过以上分析，可以得到：
假设P(i, j)表示从起点到(i, j)不踩到蘑菇的概率，那么该位置一定是从(i-1, j)或者(i, j-1)出走过来的。
而从(i-1, j)或者(i, j-1)到达(i, j)的概率是不等的，比如：如果i或者j在边界，只能向一个方向移
动，此时走到(i, j)位置的概率为1，当i或者j不在边界时，走到(i,j)的概率分别为0.5，因此可得
出：
P(i,j) = P(i-1, j) * (i==M? 1 : 0.5)+ P(i, j-1) * (j==N? 1 : 0.5);
如果(i, j)为蘑菇时，表示不能走到该位置
#include <iostream> using namespace std; #include <vector> int main() { int m, n, k; while (cin >> n >> m >> k) { // 因为地图大小已经确定好了，map直接设置好大小 vector<vector<int>> map(n + 1, vector<int>(m + 1)); // 向地图中放入蘑菇 int row, col; while (k--) { cin >> row >> col; map[row][col] = 1; } vector<vector<double>> dp(n + 1, vector<double>(m + 1));//表示概率 dp[1][1] = 1.0;//自己初始的位置 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; ++j) { // 对于每个位置，按照上述转移方程来确定概率 if (!(i == 1 && j == 1)) dp[i][j] = dp[i - 1][j] * (j == m ? 1 : 0.5) + dp[i][j - 1] * (i == n ?1 : 0.5); // 如果该位置为蘑菇，表示不能到达该位置，则到达该位置的概率一定为0 if (map[i][j]) dp[i][j] = 0; } } printf("%.2f\n", dp[n][m]); } return 0; }
