郑州网站推广￥做下拉去118cr,用vs2017做网站,泰安专业网站建设公司,聊城网站建设科技公司每日一道算法题之不同的子序列 一、题目二、思路三、C代码 一、题目
题目来源#xff1a;LeetCode【难度#xff1a;困难】 给你两个字符串 s 和 t #xff0c;统计并返回在 s 的 子序列 中 t 出现的个数#xff0c;结果需要对 109 7 取模。 示例如下#xff1a;
输入代码 一、题目
题目来源LeetCode【难度困难】 给你两个字符串 s 和 t 统计并返回在 s 的 子序列 中 t 出现的个数结果需要对 109 7 取模。 示例如下
输入rabbbitrabbit
输出3二、思路 按照动态规划的解题步骤 确定dp数组的含义 dp[i][j]:以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。 确定递推公式 分两种情况进行讨论一种是s[i-1]与t[j-1]相等一种是s[-1]与t[j-1]不相等的情况。
if(s[i-1]t[j-1]){dp[i][j]dp[i-1][j-1]dp[i-1][j];}else{dp[i][j]dp[i-1][j];}dp数组初始化 for(int i0;iN;i){dp[i][0]1;} for(int j1;jM;j){dp[0][j]0;}确定遍历顺序 遍历的顺序一定是从上到下从左到右。 三、C代码
#includebits/stdc.h
using namespace std;//不同的子序列
#define maxn 10010
int dp[maxn][maxn]; //以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。int main(){string s,t;cinst;int Ns.size();int Mt.size();//dp数组初始化for(int i0;iN;i){dp[i][0]1;} for(int j1;jM;j){dp[0][j]0;}//确定递推公式for(int i1;iN;i){for(int j1;jM;j){if(s[i-1]t[j-1]){dp[i][j]dp[i-1][j-1]dp[i-1][j];}else{dp[i][j]dp[i-1][j];}}} coutdp[N][M];}
