[LeetCode] Giải Target Sum với Python | Quy Hoạch Động Cái Túi Phần 1
ฝัง
- เผยแพร่เมื่อ 24 ก.ย. 2024
- #coding #algorithm #leetcode #laptrinh #dequy #dynamicprogramming #quyhoachdong
Leetcode problem: 494. Target Sum
leetcode.com/p...
TIMESTAMP
0:44 - Đề Bài
2:12 - Giải thích Cách Làm
4:22 - Code Cách 1 (Đệ Quy)
8:01 - Dry run
10:13 - Phân tích độ phức tạp
12:41 - Code Cách 2
19:45 - Kết
Độ phức tạp tối ưu (Cách 2):
Time Complexity (Thời Gian): O(N*T)
Space Complexity (Bộ Nhớ): O(T)
Code của bài giải trong video:
github.com/tru...
----------------------------------
Tổng hợp đáp án của các câu hỏi trên Leetcode của mình:
github.com/tru...
Tổng hợp mẹo Python của mình:
github.com/tru...
![[LeetCode] Thử sức với câu hỏi của kĩ sư Google | Dùng Python Giải Shortest Bridge](http://i.ytimg.com/vi/-kZABXBLVjU/mqdefault.jpg)
![[LeetCode] Thử sức với câu hỏi của kĩ sư Google | Dùng Python Giải Shortest Bridge](/img/tr.png)
![[LeetCode] 4 Bước để giải bài Quy hoạch động (Dynamic Programming ) | Dùng Python Giải House Robber](http://i.ytimg.com/vi/YeKg_-uGD-w/mqdefault.jpg)
![[LIVE] : ONE ลุมพินี 80 | คู่เอก "รักษ์ vs ยอดนำชัย"](http://i.ytimg.com/vi/ckLMRorsMeY/mqdefault.jpg)
![[LeetCode] Giải Ones and Zeroes với Python | Quy Hoạch Động Cái Túi Phần 2](/img/n.gif)
Em có một gợi ý thế này: Sau mỗi video anh có thể giới thiệu một puzzle mới, một puzzle cùng dạng với video hiện tại hoặc 1 case mở rộng, nâng cao cho puzzle hiện tại để mọi người suy nghĩ hướng giải quyết trước, cùng nhau thảo luận khi anh đăng lên group Python trên Facebook chẳng hạn. Cá nhân người xem như em sẽ hóng anh ra video hơn để tham khảo cách giải cũng như cách anh tư duy giải quyết bài toán!
ý tưởng tuyệt vời quá em. Để a bắt đầu triển khai từ video sau luôn. 🤩
Video rất bổ ích ạ, chỉn chu từ hình ảnh cho tới nội dung. 100 điểm
Thanks em!
Rất hay và dễ hiểu ạ. Mong anh tiếp tục ra video nhiều hơn về các cách giải thuật ạ.
cám ơn anh
thanks em nha
Rất hay ạ . Mong anh ra thêm nhiều video nữa trong tương lai
Mong em giảng giải thêm vài bài toán về quy hoạch động để con anh hiểu hơn
okay anh!
Hay quá anh ơi
Thanks em nhìu nha!
hóng video của a :p
Em có thể thêm gợi ý như này được không : Anh có thể hàm 1 main vào để chạy được không ạ , e nghe thì rất dễ hiểu nhưng đến lúc để chạy hàm main thì lại không biết dùng sao cho đúng có thể là kiến thức của e còn quá hổng chưa được chắc . Em cảm ơn a đã đóng góp vào cộng đồng lập trình VN . Chúc a và gia đình mạnh khỏe.
Lần trước em cũng đã comment về ý tưởng này nhưng a vẫn chưa thực hiện được. Bắt đầu từ video sau a sẽ thực hiện một loạt ý tưởng mới từ các bạn bao gồm cả cái này luôn nha!
Mà cho em hỏi là dfs ở đây có nghĩa là depth first search hen anh? Hay chỉ là anh thường đặt như vậy thôi?
a quen tay đặt như vậy đó em. Nhưng hầu như bài nào sử dụng đệ quy thì a cũng đặt là dfs
hóng videoo mới mãi a ơi
Thanks em! 😝
Hay quá :v
từ cách 1 bạn suy luận theo logic nào để ra được cách 2 vậy ạ?
Mình thấy khó nhất chỗ suy luận này
Anh làm về lý thuyết đồ thị đi ạ
Anh có thể dạy thêm về thuật toán được không ạ ?
em có chủ đề nào muốn ôn không em ?
cách giải thích dp={0:1} khá khó hiểu
Total = 0 có 1 cách để đạt được? Tại sao biết?
vd nums = [-2] thì dp = {0:1} có nghĩa gì ở đây?
{0:1} có nghĩ là ban đầu khi mình chưa chọn số nào thì có 1 cách để tổng bằng 0 (nó chính là cách không đi qua số nào cả). Sau khi đi qua số -2 thì nó sẽ thành {2: 1, -2: 1}. Tức là sau khi đi qua 1 số thì có 1 cách để đạt được tổng 2 và 1 cách để đạt được tổng -2.
Có rõ hơn không bạn?
Ở cách sử dụng đệ quy:
- Bạn chưa chỉ ra cách lấy đáp án. Ví dụ với đầu vào là [1, 1, 1, 1, 1] và target là 3 thì đáp án là +1 +1 +1 +1 -1 chẳng hạn.
- Hoặc mình chưa biết cách, bạn giải thích giùm
Do đề không yêu cầu in phần đó ra nên mình không làm. Tuy nhiên nếu bạn muốn in ra thì bạn có thể thêm 1 biến nữa vào dfs. Đặt tên là "tracker=[]" chẳng hạn. Ở mỗi vòng recursion thì bạn append giá trị hiện tại vô tracker, nhớ `pop()` sau khi trả về từ recursion. Và in tracker ra ở đk dừng là được
sao lâu r chưa ra video v a? cho e xin fb của e với ạ.
Do a vừa bận vừa hơi lười đó em. Cái nữa là a đang suy nghĩ ra một cách làm video ngắn (
@@trunghoang-jummyegg cố gắng ra nhiều video đều hơn a nhé.
@@QuocTien79 thank em, vì em comment nên hôm nay a record một video mới. Thỉnh thoảng vô comment để a có thêm nhiều động lực nhé.
đây là facebook của a: facebook.com/trung.nang.hoang/
@@trunghoang-jummyegg các video sau nếu làm thì a giảm độ khó xuống thì số đông sẽ dễ tiếp cận nội dung hơn a ạ :)
làm sao để mình có cái đề bên phải như v trong vs code vậy a (cái description ấy ạ)
a dùng plugin có tên là leetcode, e có thể cài vào r nó sẽ hiện y chang vậy
@@trunghoang-jummyegg plugin là sao a cài sao v ạ
@@trantandatvuive đây nè em: marketplace.visualstudio.com/items?itemName=LeetCode.vscode-leetcode