Tiếp tục chuyên mục mỗi ngày một leetcode. 3 bài mình làm ngày hôm nay:
#375. (
Medium)
https://leetcode.com/problems/guess-number-higher-or-lower-ii/
#376. (
Medium)
https://leetcode.com/problems/wiggle-subsequence/
#377. (
Medium)
https://leetcode.com/problems/combination-sum-iv/
Mình sẽ share về bài Combination Sum IV:
#377. (
Medium)
https://leetcode.com/problems/combination-sum-iv/
Phân tích bài toán:
- 1 <= nums.length <= 200: Với limit nhỏ như thế này thì có 2 khả năng:
- Hoặc là độ phức tạp để giải rất cao O(2^n) hoặc thậm chí là O(n!)
- Hoặc là kết quả output rất lớn. Nên nếu để limit quá cao sẽ bị tràn số
- Để biết là dạng nào thì ta có thể thử chạy test với input lớn một tí:
- Nếu chạy lâu và ra kết quả là một số nhỏ => Trường hợp 1. Lúc này giải pháp tối ưu có lẽ là vét cạn. Các thuật toán phù hợp thường là liệt kê hoặc quay lui.
- Nếu chạy nhanh nhưng ra kết quả là một số rất lớn => Trường hợp 2. Lúc này hướng giải thì hên xui, nhưng hay gặp nhất chắc là quy hoạch động.
- Quay lại bài này, ta thấy chỉ cần tăng input lên hơi to một chút là gặp ngay lỗi:
- => Có vẻ là hướng thứ 2, vậy ta thử giải bài này bằng QHĐ
Một chút về Quy Hoạch Động:
- Mình biết với nhiều người thuật toán QHĐ là một cái gì đó cao siêu, và dường như chỉ có các bậc thánh nhân chuyên tin mới nghĩ ra cách giải.
- Cách đây 1 năm mình cũng nghĩ vậy. Nhưng sau một thời gian cày cuốc và làm quen với dạng bài này, thì mình thấy nó cũng k có gì quá cao siêu.
- Chỉ cần nắm vững hướng tư duy và pattern của nó thì có thể vận dụng trong hầu hết các trường hợp. (Dĩ nhiên trừ những bài quá khó - mình cũng bó tay và vào discuss để xem như mn thôi. Kakaka)
- Với bạn nào chưa quen thì mình suggest xem clip này về QHĐ. Đây cũng là clip giúp mình làm quen với thuật toán này:
- Về cơ bản, pattern của thuật toán QHĐ tương tự như đệ quy, hay chia để trị. Đó là kết quả của bàn toán lớn được tính từ kết quả của các bài toán con, và tiếp tục đệ quy như thế cho đến trường hợp cơ bản đã biết trước.
- Cần chú ý là một bài toán giải bằng QHĐ cần có 2 tính chất:
- Các bài toán con phải gối nhau: Thì việc lưu lại kết quả của các bài toán con mới có ý nghĩa tối ưu. Không thì nó chỉ là chia để trị thôi.
- Cấu trúc con tối ưu: Kết quả tối ưu của bài toán lớn phải tính được từ kết quả tối ưu của các bài toán con. Nếu không thì có lưu lại kết quả của bài toán con cũng vô nghĩa.
Quay lại bài toán, ta thử áp dụng cách tiếp cận QHĐ để giải bài này:
- Để đếm số lượng các combinations có tổng bằng target, ta có thể tính nó từ kết quả của bài toán con hay không ?
- Vậy bài toán con ở đây là gì ? Hiểu nôm na đó là bài toán tương tự như bài toán gốc, nhưng với input "nhỏ" hơn
- "Nhỏ" ở đây không nhất thiết là nhỏ hơn về mặt toán học. Mà là input đó "gần" với "trường hợp cơ bản" hơn.
- "Trường hợp cơ bản" có nghĩa là các trường hợp mà từ đó ta có thể suy ra kết quả ngay lập tức, không cần phải thực hiện việc đưa về bài toán nhỏ hơn nữa.
- Quay lại, trong trường hợp này, bài toán con có thể là:
- Cũng với mảng input đó, nhưng target là một số nhỏ hơn
- Vẫn target đó, nhưng input ít đi một / một vài phần tử
- Ở đây ta thấy một phần tử có thể được dùng lại nhiều lần, nên xem ra hướng thứ hai khó khả thi. Nếu follow theo hướng thứ nhất, "target thấp hơn" thì "trường hợp cơ bản" sẽ là gì. Ta cứ nghĩ đến các case đơn giản nhất ?
- Đào sâu thêm một chút thì ta có thể tổng quá hóa thành như thế này:
- Vậy đưa về bài toán nhỏ hơn như thế nào ? Cái này gọi là "công thức truy hồi" và theo mình cũng là phần khó nhất của một bài QHĐ. Làm được hay không là ở chỗ bạn phải nhìn ra công thức này.
- Với mình, cách đơn giản là cứ execute một ví dụ và cố gắng thử tính bài toán lớn từ kết quả bài toán nhỏ. Ví dụ nums = [1, 2, 3]; target = 4:
- Giả sử ta biết số cách tạo ra "target = 3" đi, liệu ta có thể áp dụng nó để tính cho "target = 4" ?
- Đương nhiên có thể, dễ thấy giả sử có n cách để tạo ra "target = 3", ta chỉ việc cộng 1 vào mỗi cách đó để tạo ra "target = 4". Vì có số 1 nằm trong mảng input.
- Ồ. Vậy tổng quát hóa lên, nếu ta biết được có n cách tạo ra "target = x" thì cũng sẽ có n cách để tạo ra "target = k", nếu như "k - x" có nằm trong mảng input.
- Nghĩ ngược lại có vẻ sẽ hay hơn. Ta tính luôn với mỗi số x nằm trong mảng input thì sẽ có thêm combinationSum(k - x) cách để tạo ra số k.
- Nhưng cũng cần chú ý thêm edge case, nếu x = k luôn thì sao, khi đó vẫn có 1 cách để tạo ra số k, là chọn chính nó. Nhưng combinationSum(k - x) sẽ trả về 0 (vì 0 < nums[0]). Thôi thì ta thêm exception cho case này vậy.
- Vậy kết quả là tổng các combinationSum(k - x) với mỗi x trong mảng input.
Solution:
- Mình thích sử dụ Memoization, vì thấy nó gần hơn với suy nghĩ tự nhiên của con người
- Sort lại nums, lưu mảng nums đã sort lại
- Viết hàm đệ quy countCombination để tính
- Nếu target == 0: return 1
- Nếu target < nums[0]: return 0
- Nếu k == nums[0]: return 1
- Nếu target này đã được tính trước đó (nằm trong bảng kết quả), trả kết quả đã tính từ trước
- Tính kết quả bằng tổng các countCombination(k - x) với mỗi x trong mảng input.
- Lưu kết quả lại vào bảng kết quả, chú ý đây là bước quan trọng và thể hiện bản chất của quy hoạch động
- Trả về kết quả đã tính toán
Python:
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
nums.sort()
self.nums = nums
return self.countCombination(target, {})
def countCombination(self, target, memo):
if target == 0:
return 1
if target < self.nums[0]:
return 0
if target == self.nums[0]:
return 1
if target in memo:
return memo[target]
memo[target] = sum(self.countCombination(target - x, memo) for x in self.nums)
return memo[target]
p/s: Bài này thật ra khá kinh điển. Mình cố ý chọn nó và viết chi tiết để các bạn mới có thể học được cách tư duy và hướng phát triển vấn đề, thay vì chỉ đưa solution. Đồng thời solution bên trên chỉ đạt mức "
faster than 11%". Nghĩa là còn có nhiều điểm có thể tối ưu cũng như viết gọn lại. Các bạn cứ đóng góp thoải mái. Welcome.
