[LeetCode] 4 Bước để giải bài Quy hoạch động (Dynamic Programming ) | Dùng Python Giải House Robber

#coding #algorithm #leetcode #laptrinh #dequy #dynamicprogramming #quyhoachdong
Leetcode problem: 198. House Robber

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:

----------------------------------
Tổng hợp đáp án của các câu hỏi trên Leetcode của mình:

Tổng hợp mẹo Python của mình:

[HOA-NGUYEN-DEV]

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.

[ttth]

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 ạ

[trunghoang-jummyegg]

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.

[trunghoang-jummyegg]

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.

[trunghoang-jummyegg]

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

[ngotuananh]

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!

[trunghoang-jummyegg]

Đừ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.

[mon.geometrydash]

Hữu ích, dễ hiểu cho các bạn thi HSG như em ạ:)) Tks

[thienphan]

Đỉnh luôn anh ơi. Xem một video mà thành fan luôn. Rất dễ hiểu 🥰🥰

[anloc]

anh giảng rất hay❤
rất mong a ra video về leetcode graph hoặc là lí thuyết graph

[AnhVoVanHuynh]

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ề

[toanho]

Rất bổ ích, cảm ơn anh đã làm video <3

[QuocThangStudio]

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 ạ

[hieuphitrung]

video rất hay, chi tiết và bổ ích a ơi. Cảm ơn anh nhiều ạ

[roxkingreus]

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 ạ

[nhivo]

e muốn in ra chuỗi nhà bị cướp thì làm sao ạ
như là cái ex1 của 1, e muốn output: [1, 3]
thì làm sao ạ

[idkwhattoputhere_yt]

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?

[suneosama]

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 😢

[trantandatvuive]

sao a chỉ chuyển mouse linh hoạt hay vậy ạ

[suneosama]

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