[leetcode712] Minimum ASCII Delete Sum for Two Strings
2024-08-25 04:10:25
public int minimumDeleteSum(String s1, String s2) {
/*
标准的动态规划题目,难点在于想出将两个字符串删除到相同的过程
这里从两个字符串的开头字符考虑,一个一个得考虑到最后一个,我们用二维数组dp[i][j]代表字符串1前i个字符和字符串2前j个字符实现相同所需要
删除的ASCII value,有三种方法可以到达dp[i][j]:
1.dp[i-1][j] + str1[i]:由于从dp[i-1][j]到dp[i][j]是多考虑了str1的一个字符,但是str2字符数没变,所以要想相同,必须删除str[i],考虑value的话就是加上str[i]
2.dp[i][j-1] + str1[j]:对应于1,这个是多考虑str2的一个字符,所以要删除str2[j]
3.dp[i-1][j-1] + a,这里是考虑两个str都加了一个,所以str1[i] =str2[j]时,a=0;str1[i] !=str2[j]时,两个都要删除,a=str1[i] +str2[j]
这三种情况每次比较出最小的来,最后返回dp[str1.length][str2.length](这里字符串下标从1开始,因为我们考虑dp数组的第0行代表str1还啥也没有,第0列代表str2啥也没有)
*/
int m = s1.length();
int n = s2.length();
int[][] dp = new int[m+1][n+1];
//初始化动态数组,就是第0行数据和第1行数据,注意由于下标从1开始,所以charAt的时候要-1
for (int i = 1;i < m+1;i++)
dp[i][0] = dp[i-1][0] + s1.charAt(i-1);
for (int i = 1;i < n+1;i++)
dp[0][i] = dp[0][i-1] + s2.charAt(i-1);
for (int i = 1;i < m+1;i++)
{
for (int j = 1;j < n+1;j++)
{
//先看s1[i]和s2[j]是不是相等,确定a
int a =(s1.charAt(i-1) == s2.charAt(j-1))? 0 : s1.charAt(i-1)+s2.charAt(j-1);
//比较三种情况
dp[i][j] = Math.min(dp[i-1][j-1]+a,Math.min(dp[i-1][j] + s1.charAt(i-1),dp[i][j-1] + s2.charAt(j-1)));
}
}
return dp[m][n];
}
最新文章
- 简单所以不要忽视,关于\r\n和\n程序员应了解的实际应用
- VS2017 RC IIS Express 无法启动 环境不正确
- python标准模块(二)
- php部分--操作MySQL 增删改查
- snmptrap使用
- simple水平导航条
- (转)持续化集成工具CruiseControl.NET
- HttpContext.Current.Session=null问题
- 图像显示 imshow()[OpenCV 笔记5]
- 网络编程(学习整理)---2--(Udp)实现简单的控制台聊天室
- Python爬取百度贴吧数据
- iOS sourceTree忽略掉必要的xcuserdata文件
- python文件基本操作(读,写,追加)
- java 泛型的类型擦除与桥方法
- Springboot+mybatis中整合过程访问Mysql数据库时报错
- mybatis动态sql之foreach标签
- ffmpeg 处理视频项目中用到的一些命令
- Spring Aop 代理
- 【bzoj5183】[Baltic2016]Park 离线+对偶图+并查集
- Tomcat热部署,Web工程中线程没有终止