Cách các bạn suy nghĩ về 1 bài toán Đệ Quy hay là Qui Hoạch Động

mrmike612 · June 23, 2015, 7:55pm

Xin chào các bạn, mình đang học thuật toán, mình tìm hiểu về Recursion (Đệ quy) và Dynamic Programming ( Quy hoạch động). Mình cũng nắm được cơ bản về khái niệm của 2 thuật toán này. Những bài toán recursion dễ, chẳng hạn như Fibonacci, factorial…mình có thể hiểu được và làm được, nhưng qua những bài toán phức tạp hơn thì mình không thể nào tìm được cách giải hoặc tồi tệ hơn là coi bài giải cũng không hiểu luôn.

Ví dụ như 1 trong bài toán trong link sau: http://stackoverflow.com/questions/25101870/algorithm-coin-changing-code-mistake.

Bài này thực sự cũng là đơn giản nhưng mình vẫn chưa hiểu được ý tưởng của thuật toán. Mình cũng thử in kết quả ra debug nhưng quả thực cũng không thể hiểu được tại sao lại như vậy.

Kể cả với thuật toán DP, mình cũng bị tương tự. Mong các bạn nào đã từng học qua rồi có thể cho mình biết hướng suy nghĩ của bạn hoặc cách giải quyết khi bạn gặp 1 vấn đề khi áp dụng 2 loại thuật toán này.

Cảm ơn các bạn.

Gio · June 23, 2015, 4:51pm

Nói về hướng tìm thuật toán thì khá khó. Nếu bạn thường xuyên làm bài tập thì bạn có thể dễ tìm dc hướng đi đúng hơn. Nếu một bài toán mới trong lập trình thì hướng đầu có lẽ là đoán DPT của giải thuật.

Ví dụ như trong đề trên, vì yêu cầu tính tất cả tập hợp thoã mãn đề bài nên có thể ước tính yêu cầu dpt là 2^n. Bạn có thể dùng pp sinh các tập hợp có tổng=n hoặc dùng đệ quy(sẽ loại dc 1 số TH nên nhanh hơn).
Mình có thể nói cách hiểu của mình về thuật toán họ đưa ra:

ở lần xét của chỉ số i, giá trí của tổng trước là sum thì sẽ có 3 th: sum<0 thoát khỏi vì tổng các đồng tiền >n. Sum=0: đếm kq tăng lên và thoát ct( tổng sau sẽ>n nên k cần tính nữa)

Sum >0. Ở đây các đồng tiền trước đó đã sử dụng rồi nên sẽ đệ quy với foo(coin_deno…,size,i,sum-coin_deno[i])

snt2523 · June 23, 2015, 5:27pm

Không liên quan nhưng cho em hỏi : Đệ quy hay Quy hoạch động có áp dụng nhiều trong app, game không ?
Làm app, game sử dụng engine nên không biết có động đến gì 2 thằng này không nhỉ ?

tntxtnt · June 23, 2015, 5:35pm

game sử dụng engine thì chắc ko cần qhđ lắm, chừng nào code engine thì có lẽ mới cần.

snt2523 · June 23, 2015, 5:42pm

Thế còn thuật toán sinh hoặc vét cạn thì sao ? @tntxtnt
Giải toán lập trình thì có sử dụng nhiều nhưng còn làm game thì…k biết

tntxtnt · June 23, 2015, 6:22pm

game đủ các thể loại nói chung chung ai mà đưa ra câu trả lời chính xác 100% được, vd game cờ vua, cờ tướng, sudoku, rpg, fps, rts, turn-based, game quản lý, v.v… Vét cạn thì lúc nào cũng hữu dụng vì nó dễ hiểu. Pp sinh thì chắc chả cần. Cứ thuật toán về đồ thị (graph).mà táng.