mình đang học về QHD và đang làm vài bài tập và nó có 1 bài như thế này:
Cho n số tự nhiên A1,A2,…,AN. Ban đầu các số được đặt liên tiếp theo đúng thứ tự cách nhau bởi dấu “?”: A1 ? A2 ? ... ? AN . Cho trước số nguyên S, có cách nào thay các dấu ? bằng dấu + hay dấu − để được một biểu thức số học cho giá trị là S không?
mình suy nghĩ mấy ngày rồi mà chưa có hướng giải quyết sao cho đúng, xin mọi người cho mình ý tưởng để giải quyết bài này với !
Cách giải quyết dễ nhất là thử hết mọi khả năng (Brute force) bằng cách dùng đệ quy. Theo cách này thì bạn sẽ thử phép cộng và trừ với mỗi phần tử trong dãy. Khi bạn gọi đệ quy theo cách này, bạn sẽ xây dựng một cây nhị phân (Binary Tree) mà trong đó mỗi một node là một trong hai khả năng (+ hoặc -) và duyệt theo chiều sâu (Depth First Search). Bài toán hoàn thành khi bạn duyệt qua tất cả các nhánh trong cây này và tìm ra nếu có một hoặc nhiều nhánh thỏa mãn điều kiện ban đầu (bằng với S). Tuy nhiên, cách làm này có nhược điểm là độ phức tạp cao (độ phức tạp thời gian là O(2^n) với n là chiều dài của dãy số ban đầu).
Để giảm độ phức tạp, bạn có thể cải tiến thuật toán bằng cách nhớ các vị trí đã duyệt qua và kết quả tại các vị trí đó (bởi vì khi đệ quy thì có nhiều lần gọi trùng lặp). Và nếu ở tại một vị trí bất kỳ của cây, bạn có kết quả trùng với kết quả đã tính trước đó thì thuật toán không cần tính lại mà chỉ cần look up kết quả đã lưu. Cách làm này được gọi là đệ quy có ghi nhớ (Recursion with memoization). Dùng cách này thì độ phức tạp được cải thiện nhiều (O(l*n) thay vì O(2^n) với l là chiều dài của mảng trung gian dùng để ghi nhớ các kết quả trong quá trình đệ quy).
Hai cách trên này tương đối dễ hiểu hơn so với cách dùng quy hoạch động, tuy vậy nó có thể không đúng yêu cầu của bạn. Nếu muốn, bạn có thể tham khảo thêm tại Leetcode (có bao gồm mã chi tiết):
Hai phương pháp tôi đề cập ở trên là lời giải số 1 và 2 tại Leetcode, còn lời giải số 3 và 4 là dùng quy hoạch động. Dùng quy hoạch động thì thuật toán đẹp hơn (và hại não hơn …), nhưng độ phức tạp thì vẫn không hơn cách số 2 - vì vậy tôi không giải thích chi tiết ở đây. Cũng xin lưu ý là đề bài tại Leetcode có 2 ràng buộc là:
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?
