thảo luận [Học Tập] Topic thuật toán

_Gia_Cat_Luong_ đã nói:

Tiếp tục chuyên mục mỗi ngày một leetcode. 4 bài mình làm ngày hôm nay:

#371. (Medium) https://leetcode.com/problems/sum-of-two-integers/
#372. (Medium) https://leetcode.com/problems/super-pow/
#373. (Medium) https://leetcode.com/problems/find-k-pairs-with-smallest-sums/
#374. (Easy) https://leetcode.com/problems/guess-number-higher-or-lower/

Mình sẽ share về bài Find K Pairs with Smallest Sums:
#373. (Medium) https://leetcode.com/problems/find-k-pairs-with-smallest-sums/

Phân tích bài toán:

• 1 <= nums1.length, nums2.length <= 10^4: Độ phức tạp kì vọng có lẽ là O(nlogn)
• Dữ liệu đã sắp xếp sẵn nên không cần sắp xếp lại
• Đề bài yêu cầu lấy ra k cặp số có tổng nhỏ nhất, từ 2 mảng
• Dễ thấy cặp số nhỏ nhất chắc chắn là 2 phần tử đầu tiên của 2 mảng (nums1[0], nums2[0])
• Với cặp số thứ 2, đó có thể là (nums1[1], nums2[0]) hoặc (nums1[0], nums2[1]). Tùy theo cái nào nhỏ hơn.
• Với cặp số thứ 3, nó phụ thuộc vào cách ta chọn cặp số thứ 2, các khả năng có thể là
  • (nums1[1], nums2[1]) và (nums1[0], nums2[2]). Nếu lần trước ta chọn cặp (nums1[0], nums2[1])
  • (nums1[1], nums2[1]) và (nums1[2], nums2[0]). Nếu lần trước ta chọn cặp (nums1[1], nums2[0])
• Đến đây ta rút ra 2 kết luận:
  • Nếu lần trước ta chọn cặp số thứ (nums1, nums1[j]). Thì tiếp theo sẽ phát sinh thêm 2 khả năng (nums1, nums2[j + 1]) hoặc (nums1[i + 1], nums2[j])
  • Pattern ở đây là có một mảng các số (là tổng của cặp số), và ta liên tục lấy ra các số số nhỏ nhất, không quan tâm các số còn lại => Phù hợp với cấu trúc dữ liệu heap

Solution:

• Khởi tạp heap với cặp đầu tiên là (0, 0)
• Lặp cho đến khi lấy được k kết quả, hoặc hết heap
  • Lấy kết quả nhỏ nhất ra, cho và mảng output
  • Thay thế nó bằng 2 khả năng mới là (i + 1, j) và (i, j + 1)
• Return về mảng output

Python:

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        j = [0] * len(nums1)
        h = [(nums1[0] + nums2[0], 0, 0)]
     
        visited = set()
        res = []
        while h and len(res) < k:
            val, i, j = heappop(h)
            res.append([nums1[i], nums2[j]])
         
            if i < len(nums1) - 1 and (i + 1, j) not in visited:
                heappush(h, (nums1[i + 1] + nums2[j], i + 1, j))
                visited.add((i + 1, j))
             
            if j < len(nums2) - 1 and (i, j + 1) not in visited:
                heappush(h, (nums1[i] + nums2[j + 1], i, j + 1))
                visited.add((i, j + 1))
             
        return res

Nhấp để mở rộng...

Ngày Được Tự Do đã nói:

sao lại nghĩ ra dùng heap vậy fen

Nhấp để mở rộng...

_Gia_Cat_Luong_ đã nói:

Tại mình đang thất nghiệp mà fen, thời gian để ôn luyện thôi .
Luyện leetcode hay k nó cũng tùy thuộc vào plan của bác nữa:

• Muốn target vào FAANG: Phải luyện all level. Bài hard cũng phải làm trôi được 80%.
• Muốn vào EU & US: Luyện đến medium thôi chắc cũng đủ rồi. Làm hard hao não lắm mà ng ta cũng k phỏng vấn đến đó
• Luyện cho market VN: Chẹp, chắc là lên mạng gg các bài code thường gặp khi phỏng vấn thì tốt hơn. VN k pv leetcode.
• Luyện để cải thiện khả năng tư duy & code thực tế: Làm mấy bài easy là đủ

Khi luyện thì bác cứ chọn theo từng chủ đề, mỗi chủ đề làm khoảng 4 5 bài tới khi thấy quen pattern rồi thì switch qua chủ đề khác. Làm tới khi nào thấy thuận tay với hầu hết các bài (trong mức level mình target) là ổn. Lúc đó thì nâng level lên hoặc cứ làm random thôi.

Nhấp để mở rộng...

_Gia_Cat_Luong_ đã nói:

Chắc là làm nhiều thì quen pattern thôi. Cứ gặp bài toán pick ra n số lớn nhất / nhỏ nhất từ một cái mảng biến động (thêm / xóa liên tục) thì nghĩ đến heap thôi.
Một cách khác là nhấn vào mục Related topics, nó có tag Heap thì tiếp cận theo hướng đó thôi. Lâu lâu bí quá mình vẫn hay xài cách này .

Nhấp để mở rộng...

_Gia_Cat_Luong_ đã nói:

Tại mình đang thất nghiệp mà fen, thời gian để ôn luyện thôi .
Luyện leetcode hay k nó cũng tùy thuộc vào plan của bác nữa:

• Muốn target vào FAANG: Phải luyện all level. Bài hard cũng phải làm trôi được 80%.
• Muốn vào EU & US: Luyện đến medium thôi chắc cũng đủ rồi. Làm hard hao não lắm mà ng ta cũng k phỏng vấn đến đó
• Luyện cho market VN: Chẹp, chắc là lên mạng gg các bài code thường gặp khi phỏng vấn thì tốt hơn. VN k pv leetcode.
• Luyện để cải thiện khả năng tư duy & code thực tế: Làm mấy bài easy là đủ

Khi luyện thì bác cứ chọn theo từng chủ đề, mỗi chủ đề làm khoảng 4 5 bài tới khi thấy quen pattern rồi thì switch qua chủ đề khác. Làm tới khi nào thấy thuận tay với hầu hết các bài (trong mức level mình target) là ổn. Lúc đó thì nâng level lên hoặc cứ làm random thôi.

Nhấp để mở rộng...

clonemasteruwu đã nói:

Cốc cốc search phỏng vấn leetcode đó medium ++

Nhấp để mở rộng...

clonemasteruwu đã nói:

Cốc cốc search phỏng vấn leetcode đó medium ++

Nhấp để mở rộng...

KimSoHyunGoddness đã nói:

Xem tệp đính kèm 675371
em mới giải bài easy này mà trầm cảm luôn á mấy bác.

Nhấp để mở rộng...

class Solution {
public:
    string frequencySort(string s) {
        int mmap[256] = {0};
   
        for(auto c: s) mmap[c]++;
         
        std::sort(s.begin(), s.end(), [&mmap](char a, char b) {    
            return mmap[a] != mmap[b] ? mmap[a] > mmap[b] : a < b;
        });
   
        return s;
    }
};

Fire Of Heart đã nói:

Bài này medium mà....

mà sao bạn code rối rắm thế zzzz

C++:

class Solution {
public:
    string frequencySort(string s) {
        int mmap[256] = {0};
   
        for(auto c: s) mmap[c]++;
         
        std::sort(s.begin(), s.end(), [=](char a, char b) {    
            return mmap[a] != mmap[b] ? mmap[a] > mmap[b] : a < b;
        });
   
        return s;
    }
};

Nhấp để mở rộng...

clonemasteruwu đã nói:

capture by value vầy mà thay cái array bằng cái vector thì bứt nắp performance đó nếu chỉ so sánh mà k modify thì prefer capture by reference nha

Nhấp để mở rộng...

Fire Of Heart đã nói:

Uh đúng rồi, nãy ko để ý

Nhấp để mở rộng...

clonemasteruwu đã nói:

https://stackoverflow.com/questions/15423695/can-you-capture-arrays-in-a-lambda
Bình thường cứ assume là array sẽ decay thành pointer trước khi được copy, sáng nay mới biết capture by value array copy hết các element

Nhấp để mở rộng...

class Solution {
public:
    string frequencySort(string s) {
        vector<int> counts (128, 0);
       
        for(auto c: s) ++counts[c];
       
        vector<pair<int, char>> v;
       
        for(int i = 0; i < 128; i++) {
            if(counts[i] != 0) {
                v.push_back(pair<int, char> (counts[i], i));
            }
        }
        sort(v.rbegin(), v.rend());
        string r;
        for(auto &kv:v) {
            r.append(kv.first, kv.second);
        }
        return r;
       
    }
};

Fire Of Heart đã nói:

À, chỗ kia mình ban đầu để [&mmap] là nó nhanh hơn 1 khúc (28ms) ^^ sau sửa lại [=] lúc nào ko rõ, thì chậm hơn hẳn (40ms).

Còn với array, nếu pass ko dùng reference thì nó copy nguyên array.

zz lâu ko code c++ nhớ là thế

btw, best perf (4ms)

C++:

class Solution {
public:
    string frequencySort(string s) {
        vector<int> counts (128, 0);
     
        for(auto c: s) ++counts[c];
     
        vector<pair<int, char>> v;
     
        for(int i = 0; i < 128; i++) {
            if(counts[i] != 0) {
                v.push_back(pair<int, char> (counts[i], i));
            }
        }
        sort(v.rbegin(), v.rend());
        string r;
        for(auto &kv:v) {
            r.append(kv.first, kv.second);
        }
        return r;
     
    }
};

Nhấp để mở rộng...

Fire Of Heart đã nói:

Bài này medium mà....

mà sao bạn code rối rắm thế zzzz

C++:

class Solution {
public:
    string frequencySort(string s) {
        int mmap[256] = {0};
  
        for(auto c: s) mmap[c]++;
        
        std::sort(s.begin(), s.end(), [&mmap](char a, char b) {   
            return mmap[a] != mmap[b] ? mmap[a] > mmap[b] : a < b;
        });
  
        return s;
    }
};

Nhấp để mở rộng...

• 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:

The answer should fit in a 32-bit integer.

Nhấp để mở rộng...

• => Có vẻ là hướng thứ 2, vậy ta thử giải bài này bằng QHĐ

• 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.

• Để đế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 ?

Ví dụ với example input nums = [1, 2, 3] và target = 4. Ta muốn tìm trường hợp cơ bản khi "target" thấp hơn:

• target = 0 => Dễ thấy không có cách nào tạo ra cả, vì mọi số trong mảng đều lớn hơn 0
• target = 1 => Có một cách duy nhất. Vì trong mảng có một số 1. Còn lại đều lớn hơn 1 cả.
• target = 2 => Bắt đầu phức tạp rồi, chắc không còn cơ bản nữa :v

Nhấp để mở rộng...

• Đào sâu thêm một chút thì ta có thể tổng quá hóa thành như thế này:

• Đầu tiên sort lại mảng nums tăng dần
• Nếu target < nums[0] => return 0
• Nếu target == nums[0] => return 1
• Nếu target > nums[0] => Không phải trường hợp cơ bản nữa, ta cần nghĩ ra cách để giải nó bằng bài toán nhỏ hơn

Nhấp để mở rộng...

• 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.

• 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

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]

_Gia_Cat_Luong_ đã nói:

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.

Nhấp để mở rộng...

_Gia_Cat_Luong_ đã nói:

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.

Nhấp để mở rộng...

_Gia_Cat_Luong_ đã nói:

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/

Nhấp để mở rộng...

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {

        vector<unsigned int> dp (1001, 0);
        dp[0] = 1;
        for(int i = 1; i <= target; i++) {
            for(auto c: nums) {
                if(i>=c) dp[i] += dp[i-c];
            }       
        }
   
        return dp[target];
   
    }
};