动态规划-Distinct Subsequences
2024-09-05 10:02:03
2020-01-03 13:29:04
问题描述:
问题求解:
经典的动态规划题目,一般来说dp题目是递推关系公式难想,但是实际代码量还是比较少的。
有尝试过dfs来做,但是由于时间复杂度是指数级别的,所以会TLE。
public int numDistinct(String s, String t) {
int n1 = s.length();
int n2 = t.length();
int[][] dp = new int[n2 + 1][n1 + 1];
for (int i = 0; i <= n1; i++) dp[0][i] = 1;
for (int i = 1; i <= n2; i++) {
for (int j = 1; j <= n1; j++) {
if (t.charAt(i - 1) == s.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
else dp[i][j] = dp[i][j - 1];
}
}
return dp[n2][n1];
}
最新文章
- UpdatePanel无法导出下载文件
- VS2013 Community配置OpenCV3.0.0
- [LeetCode] Range Sum Query - Immutable &; Range Sum Query 2D - Immutable
- Docker CPU 资源限制——CPU固定核功能测试
- Context3D 不可用
- LINUX进程优先级实现
- JDBC与javaBean
- Watchcow
- 关于PagedDataSource分页属性与DataSet和DataTable详解
- 在将 varchar 值 &#39;2,7&#39; 转换成数据类型 int 时失败
- Java-二进制转10进制原理机制
- 678 ";流浪地球";为什么是个好地方?(系统越复杂拥有好运气的机会也就越大)
- <;<;梦断代码>;>;阅读笔记三
- 使用Wisdom RESTClient进行自动化测试,如何取消对返回的body内容的校验?对排除的JSON属性字段不做校验?
- python3+ftplib实现ftp客户端
- nginx-ngx_http_random_index_module
- 卸载或安装程序出现:The feature you are trying to use is on a network resource ...
- (转)Linux磁盘空间监控告警 &;&; Linux磁盘管理
- OA环境搭建及卸载操作帮助文档
- IIS设置问题