[LeetCode] 4 Bước để giải bài Quy hoạch động (Dynamic Programming ) | Dùng Python Giải House Robber
HTML-код
- Опубликовано: 13 сен 2024
- #coding #algorithm #leetcode #laptrinh #dequy #dynamicprogramming #quyhoachdong
Leetcode problem: 198. House Robber
leetcode.com/p...
TIMESTAMP
1:01 - Đề Bài
3:26 - Code Cách 1
11:07 - Code Cách 2
16:54 - Mẹo Đệ quy
18:26 - Giải thích Cách 3
22:28 - Code Cách 3
27:11 - Code Cách 4
31:08 - Tóm tắt 4 Bước để giải bài Quy hoạch động
33:40 - Kết
Độ phức tạp tối ưu (Cách 4):
Time Complexity (Thời Gian): O(N)
Space Complexity (Bộ Nhớ): O(1)
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] Dùng Python giải Single Element in a Sorted Array | Tìm kiếm nhị phân](http://i.ytimg.com/vi/yGD3J7uz02k/mqdefault.jpg)
![[LeetCode] Dùng Python giải Single Element in a Sorted Array | Tìm kiếm nhị phân](/img/tr.png)
Không có câu hỏi gì là ngu ngốc. Các bạn có câu hỏi gì thì cứ thoải mái comment, mình sẽ giải đáp hết tất cả thắc mắc cho các bạn dù nó đơn giản đến đâu đi nữa.
trog thực tế có bài làm quy hoạch không anh ,và làm sao nhận biết được bài ý là bài quy hoạch động ạ
@@CongNguyen-fi5cd trên thực tế. Ít khi em gặp những bài toán kiểu này lắm. Tuy nhiên, đi phỏng vấn, nhiều công ty vẫn sẽ hỏi
@@CongNguyen-fi5cd trên thực tế thì quy hoạch động chỉ dùng để optimize cho app thôi em.
Trừ khi app của em yêu cầu performance tối ưu từ ban đầu, chỉ cần app chạy là được.
Đến lúc cần optimize thì ta optimize nó. Quy hoạch động là một trong những cách để optimize thôi em .
Tóm tắt 4 bước để giải 1 bài Dynamic Programming (Quy hoạch động):
1. Giải theo hướng đệ quy:
Đây sẽ là cách dễ nhất để bắt đầu một bài DP. Ở bước này thì bạn không cần quan tâm đến độ phức tạp. Chỉ cần trả đúng giá trị là okay rồi. Thường thì độ phức tạp của bước 1 sẽ là khoảng O(2^N) hoặc O(N!)
2. Top-down DP:
Vì khi sử dụng đệ quy, sẽ có nhiều hàm bị gọi đi gọi lại nhiều lần, chúng ta có thể cải thiện bằng cách sử dụng thêm bộ nhớ để lữu giữ giá trị trả về của các hàm đã tính. Như thế, ở những lần gọi tiếp theo, chúng ta sẽ sử dụng giá trị trong bộ nhớ thay vì tính lại từ đầu mất thời gian. Đa số mọi người sẽ dừng ở bước này. Do là độ phức tạp thời gian đã tối ưu rồi. Các bước sau mục đích là chỉ để cải thiện độ phức tạp không gian thôi.
3. Bottom-up DP:
Thay vì dùng đệ quy, chúng ta sử dụng mảng để chứa các giá trị và thực hiện tính toán ngay trên mảng đó. Bước 2 và 3 sẽ có chung độ phức tạp. Tuy nhiên, đây là một bước vô cùng quan trọng để có thể tiến tới bước 4 một cách dễ dàng hơn.
4. Cải thiện độ phức tạp không gian:
Dựa vào cái mảng từ bước 3, chúng ta có thể phát hiện được những giá trị mà chỉ được sử dụng cho 1-2 lần tính toán. Đối với những giá trị này, chúng ta không cần đến mảng để chứa nó làm gì. Thay vì thế, bạn hoàn toàn có thể sử dụng ít biến hơn cho việc tính toán, và chúng ta chỉ cần ghi đè lên các biến này khi nó không cần thiết nữa.
Các bạn có hứng thú với một topic nào đó thì cứ comment cho mình biết nhé. Dự tính của mình trong tương lai là làm về các bài cây (Binary Tree, N-array Tree).
Quá tuyệt vời ạ, cảm ơn anh đã giảng chi tiết, từng bước phối hợp giọng nói rõ ràng cực hay nữa ạ
@@ttth4974 cảm ơn em ☺️
Đừng quên cho mình biết nếu như video đã giúp bạn hiểu hơn về DP nhé. Hoặc nếu có gì chưa tốt trong video thì mình cũng xin nhận mọi ý kiến đóng góp.
Anh giảng hay quá, coi mà không bỏ 1 giây nào luôn. Hóng video mới của anh
Phạm Đoàn Tiến cảm ơn em nhiều nha!
Cách giải thích dễ tiếp cận. Cám ơn ad nhiều , mong là có nhiều bài về đệ quy hơn.
Cảm ơn anh rất nhiều ạ.
Đỉnh luôn anh ơi. Xem một video mà thành fan luôn. Rất dễ hiểu 🥰🥰
anh giảng dễ hiểu quá 😊, thanks anh
bạn sẽ tóm tắt dynamic program
i= n dãy nhà
và v[i] = tiền của từng nhà
và với d[n+1] = mảng để lưu giá trị cướp
d[0] = 0 có nhà nào để cướp mặc định = 0
trọm sẽ bắt đầu từ nhà đầu tiên d[1] = v[1]
bắt đầu từ i =2 to n+1
if(nhà hiện tại - nhà trước đó == giá trị cướp được trước đó )
then
đối với nhà liền kề thì ta sẽ lấy giá trị trước i=i-1
else
so sánh max(i+v[i-1],i+v[i+1]) lấy nhà hiện tại hay nhà sau kề tối ưu hơn
thì i=i-1 +v[i] lấy giá trị nhà trước + với giá trị cướp được nhà hiện tại hoặc nhà tối ưu
thêm vào true hoặc false để đánh dấu nhà liền kề
Có khi bạn cũng không biết video này giúp mình nhiều như thế nào trong con đường trở thành lập trình viên đâu. Cám ơn bạn rất rất nhiều!
Cảm ơn Tuan Anh nhiều nhé 🥰!
Video rất dễ hiểu, cám ơn bạn nhiều.
Dễ hiểu cực cho anh 1 like nhé
Em cảm ơn anh vì video bổ ích này ạ
sau 1 video hiểu luôn, cảm ơn a
Rất bổ ích, cảm ơn anh đã làm video
Chuỗi video này của anh rất bổ ích ạ ^^ hy vọng anh sẽ làm thêm, em cám ơn anh rất nhiều ạ
Okay em, anh sẽ làm thêm nhiều video nữa. Thanks em.
video rất hay, chi tiết và bổ ích a ơi. Cảm ơn anh nhiều ạ
Thanks em!
anh giảng rất hay❤
rất mong a ra video về leetcode graph hoặc là lí thuyết graph
video algo hay nhất mình từng xem :D
video rat bo ich, em cam on anh
Tuyệt vời!
quá hay bạn ơi
cảm ơn ông nha hehe! keep it up
Thanks, Duy
đỉnh lắm a :3
I am your fannnnnnnnnnn !!!!!!!!
max dfs i-1, dfs i-2 + nums[i] là sao anh em ko hiểu, là nhà cướp nhà nào ta nhà cuối cùng dfs i-1 có một mình nó à sao ko phải là dfs i-1 + dfs i-3 anh, là 2 cái nhà cách nhau cộng lại 😢
Lý do mình k có i-3 và i-4 trong công thưac này là ví i-3 i-4 sẽ tự xuất hiện khi mình đệ quy. Ví dụ
Dfs(i-1) có hai option:
Dfs(i-1-1) : lấy nhà trước đó mà không lấy i-1
Dfs(i-1-2) + nums[i-1]: lấy nhà i-1 và i-3
return max(dfs(i-1), dfs(i-2) + nums[i]) anh giải thích dòng này giúp em đc ko em ko nắm đc concept ta 😢 giúp em với anh Trung Hoàng đẹp trai
Nếu mà để ghi rõ ra từng câu chữ thì là thế này:
i là vị trí nhà hiện tại. Tại nhà hiện tại mình có hai lựa chọn.
Một là lấy nhà hiện tại và nhà i-2.
Hai là lấy nhà trước đó (i-1) và bỏ qua nhà hiện tại.
Và vì đây là đệ quy. Nên e có thể hình dung là khi mình chọn option nào đi nữa thì mình cũng tiếp tục có hai lựa chọn tại vị trí. Về cơ bản thì logic đệ quy này sẽ tiếp tục mãi mãi trừ khi e có điều kiện dừng.
@@trunghoang-jummyegg à i là vị trí nhà mà cái nums[i] nó iterate, em cám ơn anh, anh Trung Hoàng đẹp trai tài năng có tâm có tầm em cám ơn anh
vip
Anh ơi a code bằng c++ đc ko ạ
Ad ơi ví dụ có 1 cái balo chứa tối đa n kg , có một vài món vật có khối lượng A[i] và giá trị B[i] thì làm sao để balo có thể chứa đầy mà giá trị món đồ thấp nhất ạ e code sao nó ra = 0 mãi ạ
cho e hỏi ạ. nếu mình tham gia các cuộc thi (hsg hay kiểu vnoi ấy) thì memory nó có ảnh hưởng chung đến total runtime không?
Cái đó a k rõ em. Nhưng a có đọc một số đề thi hsg thì người ta sẽ nêu cụ thể về limitation nếu có.
sao a chỉ chuyển mouse linh hoạt hay vậy ạ
Là sao nhi?. A k hiểu ý em lắm.
@@trunghoang-jummyegg em chat nhầm sao a gõ code linh hoạt v ạ ,khi đánh trong dấu ngoặc bay xuống hàng khác nhanh lắm luôn em thấy a không dùng vim nữa
@@trantandatvuive cũng có 1 vài lý do em ạ. Một là a cắt và chỉnh sửa video nên có thể nó trông nhanh hơn thực tế. Hai là a code nhiều và dùng vscode cũng nhiều nên quen tay.
Anh ơi để học tốt dp thì mình có nên xem solution 1 số bài trước không ạ . em mới học dp mà k nghĩ ra nổi công thức hay ý tưởng gì luôn ạ
Khi chưa biết gì thì e phải xem solution trước, đến khi em có basic vững rồi thì mới không cần đọc solution trước. DP là dạng bài cực khó cần nhiều kinh nghiệm mới giải tốt được. Có công mài sắt có ngày nên kim nha em, phải rèn một thời gian dài mới giỏi được
Anh Trung Hoàng em thấy có chỗ em ko hiểu, là cái dp em hiểu r dp[-1] r compare return max cộng tiếp, còn recursion return dfs(len(nums)-1)) nó cũng tương tự như dp[-1] đúng ko anh, em thấy chưa nắm đc khúc đó ta, đó là cách mà mình return index cuối của recursion đúng ko anh, axjba 😅😆, còn cái i là cái dfs(len(nums)-1) nó đại diện cho cái dfs(i) đúng ko anh, tại sao lại là dfs(len(nums)-1) ta là cái return index cuối cùng như dp[-1] hả anh, thứ 2 là em cái approach 2 em bỏ cái return mem[i] thì nó ko work ta(line 52) á anh, em tưởng mình lưu nó vô trong cái dòng ở trên (line51) là đc r chứ ta, mong anh giải thích 2 cái thắc mắc của em, thank anh trai ❤
cái return mem[i], nếu em bỏ nó thì sẽ là return None về hàm mẹ. E cần phải xác định e muốn return gì cho đúng thì mình code như vậy. Trong trường hợp này thì mình muốn return giá trị mà mình đã lưu trong bộ nhớ trước đó.
Còn phần dfs(len(nums)-1)) là dùng để kích hoạt vòng recusion đầu tiên (hàm mẹ trên cùng).
Về logic thì dp[-1] là dfs(len(nums)-1)) khi mình nhìn vấn đề từ đúng hướng (top-down, hoặc bottom up). Để hiểu rõ hơn thì e thử một số example khác nhau và làm bằng tay xem (viết ra giấy)
@@trunghoang-jummyegg Anh Trung Hoàng có rảnh anh làm thêm về leetcode longest line of consecutive ones với denote the maximum bomb với number of islands, em thấy mấy cái đó cover graph với dps bfs mà em ko hiểu lắm 😂 thank anh trai ❤️
@@suneosama939 a cos bài number of island nè em: ruclips.net/video/3HUVEHmM6UY/видео.html&ab_channel=TrungHo%C3%A0ng
Làm về backtracking đi a
Để a note lại r làm từ từ nhé. Thanks em !