leedcode 115. 不同的子序列
2022/6/30 23:23:32
本文主要是介绍leedcode 115. 不同的子序列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
![](/upload/202206/30/202206302323327690.png)
思路分析:
dp[i][j] 表示 s 串中使用了 i 个字符,t 串中使用了 j 个字符,s 包含 t 中子序列的个数
当 s[i] == t[j] 时,考虑当前字符是否要匹配,若匹配,方案数则是由 i-1 和 j-1 往过累加,若不匹配,则是由 dp[i-1][j] 这个状态去累加
代码示例:
class Solution { public: int numDistinct(string s, string t) { int len1 = s.length(); int len2 = t.length(); unsigned long long dp[1005][1005]; memset(dp, 0, sizeof(dp)); dp[0][0] = 1; for(int i = 1; i <= len1; i++){ dp[i][0] = 1; for(int j = 1; j <= len2; 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]; } } return dp[len1][len2]; } };
这篇关于leedcode 115. 不同的子序列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain