Giả sử ta có hai xâu s và t gồm các chữ số, ta phải tìm cách xóa các chữ số trong xâu sao cho:1. Hai xâu giống nhau 2. Tổng các chữ số bị xóa là nhỏ nhất Cuối cùng trả về tổng nhỏ nhất.
Vì vậy, nếu đầu vào là s ="41272" t ="172", thì đầu ra sẽ là 6, vì chúng ta có thể loại bỏ "4" và "2" khỏi chuỗi đầu tiên để lấy "172".
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Định nghĩa một hàm lcs (). Điều này sẽ mất a, b, m, n
-
table:=ma trận 2d có kích thước (n + 1) x (m + 1) và điền bằng 0
-
đối với tôi trong phạm vi từ 1 đến m, hãy thực hiện
-
đối với j trong phạm vi từ 1 đến n, thực hiện
-
nếu a [i - 1] giống với b [j - 1] thì
-
table [i, j]:=table [i - 1, j - 1] + 2 * (ASCII của a [i - 1] - 48)
-
-
nếu không,
-
table [i, j] =tối đa của table [i - 1, j] và table [i, j - 1])
-
-
-
-
trả lại bảng [m, n]
-
Từ phương thức chính, hãy làm như sau
-
m:=kích thước của a, n:=kích thước của b
-
c:=0
-
đối với tôi trong phạm vi từ 0 đến m, hãy thực hiện
-
c:=c + ASCII của [i] - 48
-
-
đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện
-
c:=c + ASCII của b [i] - 48
-
-
kết quả:=c - lcs (a, b, m, n)
-
trả về kết quả
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
class Solution: def lcs(self, a, b, m, n): table = [[0 for i in range(n + 1)] for j in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if a[i - 1] == b[j - 1]: table[i][j] = table[i - 1][j - 1] + 2 * (ord(a[i - 1]) - 48) else: table[i][j] = max(table[i - 1][j], table[i][j - 1]) return table[m][n] def solve(self, a, b): m = len(a) n = len(b) c = 0 for i in range(m): c += ord(a[i]) - 48 for i in range(n): c += ord(b[i]) - 48 result = c - self.lcs(a, b, m, n) return result ob = Solution() s = "41272" t = "172" print(ob.solve(s, t))
Đầu vào
"41272", "172"
Đầu ra
6