fucking-algorithm
fucking-algorithm copied to clipboard
经典动态规划:最长公共子序列 :: labuladong的算法小抄
- 两个字符串的最小ASCII删除和(中等) python版本解法
class Solution:
'''
问题等价: 求最长公共子序列的最大ASCII码值的和,
'''
def minimumDeleteSum(self, s1: str, s2: str) -> int:
dp = [[0]*(len(s2)+1) for _ in range(len(s1)+1)]
for i in range(1,len(s1)+1):
for j in range(1,len(s2)+1):
if s1[i-1] == s2[j-1]:
dp[i][j]=dp[i-1][j-1]+ord(s1[i-1])
else:
dp[i][j]=max(dp[i-1][j],dp[i][j-1])
ascSum = 0
ascSum += sum([ord(char) for char in list(s1)])
ascSum += sum([ord(char) for char in list(s2)])
return ascSum - 2*dp[len(s1)][len(s2)]
1143.C++
class Solution {
public:
// 定义dp返回 text1从i, text2从j开始的公共子序列的长度
int dp(string text1, int i, string text2, int j, vector<vector<int>>& memo)
{
if(i==text1.length() || j==text2.length())
return 0;
if(memo[i][j] != -1)
return memo[i][j];
if(text1[i]==text2[j])
memo[i][j] = 1 + dp(text1, i+1, text2, j+1, memo);
else
{
memo[i][j] = max(dp(text1, i+1, text2, j, memo),
dp(text1, i, text2, j+1, memo));
}
return memo[i][j];
}
int longestCommonSubsequence(string text1, string text2) {
// 定义备忘录
vector< vector<int> > memo(text1.size(), vector<int>(text2.size(), -1));
return dp(text1, 0, text2, 0, memo);
}
};
力扣自顶而下居然超时, 定义了备忘录也会的吗呜呜呜~
@kuangkuangkuangha 是你代码写得有问题吧,递归函数的参数怎么能传值呢?string 改成 string& 试试。
@labuladong 雀氏哦,稳啊!传参数会拷贝的,内存大,耗时,牛蛙,谢谢啦!
712 两个字符串最小ASCII删除和 自底向上dp解法
public int minimumDeleteSum(String s1, String s2) {
int m = s1.length(), n = s2.length();
//s1[...i]和s2[...j]若要成为相等的字符串所需要删除的字符的ASCII值的最小和为dp[i][j]
int[][] dp = new int[m + 1][n + 1];
//base case
for (int i = 1; i <= m; i++) {
dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
}
for (int j = 1; j <= n; j++) {
dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1);
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j] + s1.charAt(i - 1),
dp[i][j - 1] + s2.charAt(j - 1));
}
}
}
return dp[m][n];
}
打卡,感谢楼主!
请问怎么一上来就知道这题用dp的
582 题的 js 解法,习惯用空白字符给两个字符串增加前缀,避免偏移量
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
var minDistance = function (word1, word2) {
// 避免偏移量
word1 = " " + word1;
word2 = " " + word2;
const rows = word1.length;
const cols = word2.length;
// dp[i][j] 含义:到 i,j 位置时,使得字符串相同的最小步骤
const dp = new Array(rows)
.fill(0)
.map(() => new Array(cols).fill(Number.MAX_SAFE_INTEGER));
// init
dp[0][0] = 0; // 第一个字符相等,不需要操作
for (let row = 1; row < rows; row++) {
dp[row][0] = row;
}
for (let col = 1; col < cols; col++) {
dp[0][col] = col;
}
// tra
for (let row = 1; row < rows; row++) {
for (let col = 1; col < cols; col++) {
if (word1[row] === word2[col]) {
// 相等,不需要删除
dp[row][col] = dp[row - 1][col - 1];
} else {
const ifDeleteRow = dp[row][col - 1] + 1; // word2 不需要动
const ifDeleteCol = dp[row - 1][col] + 1; // word1 不需要动
dp[row][col] = Math.min(ifDeleteRow, ifDeleteCol);
}
}
}
return dp[rows - 1][cols - 1];
};
LC.712 - DP 数组自底向上
class Solution {
public int minimumDeleteSum(String s1, String s2) {
int m = s1.length(), n = s2.length();
int[][] dp = new int[m+1][n+1];
for(int i = 1; i <= m; i++){
dp[i][0] = s1.charAt(i-1) + dp[i-1][0];
}
for(int j = 1; j <= n; j++){
dp[0][j] = s2.charAt(j-1) + dp[0][j-1];
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(s1.charAt(i-1) == s2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1];
}else{
dp[i][j] = Math.min(dp[i-1][j]+s1.charAt(i-1), dp[i][j-1]+s2.charAt(j-1));
}
}
}
return dp[m][n];
}
}
内存压缩版
class Solution {
// int[][] dp;
int[] dp;
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
// dp = new int[m+1][n+1];
dp = new int[n+1];
for(int i = 1; i <= m; i++) {
int pre = 0;
for(int j = 1; j <=n; j++) {
int temp = dp[j];
if(text1.charAt(i-1) == text2.charAt(j-1)){
// dp[i][j] = 1+ dp[i - 1][j - 1];
dp[j] = 1+pre;
}else {
// dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
dp[j] = Math.max(dp[j-1],dp[j]);
}
pre = temp;
}
}
return dp[n];
}
}
东哥,向您请教一个问题:
从后往前对比两个字符串的,加上memo之后就不对了,如果东哥看到可以帮我看看哪里出问题了吗 非常感谢!!
class Solution {
int[][] memo;
public int minimumDeleteSum(String s1, String s2) {
int m = s1.length();
int n = s2.length();
memo = new int[m][n];
for(int[] mm : memo) Arrays.fill(mm, -1);
return dp(s1, m - 1, s2, n - 1, 0);
}
public int dp(String s1, int i, String s2, int j, int sum) {
// base case
if(i < 0) {
for(int k = j; k >= 0; k--){
sum += s2.charAt(k);
}
return sum;
}
if(j < 0) {
for(int k = i; k >= 0; k--) {
sum += s1.charAt(k);
}
return sum;
}
// 把从memo找的这步注掉就没问题,加上答案就不对
if(memo[i][j] != -1) return memo[i][j];
//dp
if(s1.charAt(i) == s2.charAt(j)) {
memo[i][j] = dp(s1, i - 1, s2, j - 1, sum);
} else {
memo[i][j] = Math.min(dp(s1, i, s2, j - 1, sum + s2.charAt(j)),
dp(s1, i - 1, s2, j, sum + s1.charAt(i)));
}
return memo[i][j];
}
}