Bài toán cầu thang bước hỏng -quy hoạch động - hsg lớp 6 -toán tư duy

Bài toán cầu thang bước hỏng -quy hoạch động - hsg lớp 6 -toán tư duy

Một cầu thang có 12 bậc. A có thể đi lên 1 bậc, 2 bậc, 3 bậc. Bậc thứ 4 và 8 bị hỏng. Hỏi có bao nhiêu cách đi hết cầu thang?

Đây là một bài toán quy hoạch động (dynamic programming). Chúng ta sẽ tìm số cách để leo đến từng bậc thang, sau đó sử dụng thông tin đó để tính số cách lên các bậc tiếp theo.

Gọi $dp[i]$ là số cách để đi đến bậc thang thứ $i$. Ta có:

• $dp[0]=1$ (có 1 cách để ở vị trí xuất phát, chưa đi bậc nào).
• Các bậc thứ 4 và 8 bị hỏng nên không thể đến được, do đó $dp[4]=0$ và $dp[8]=0$.

Để leo lên bậc thứ $i$ (với $i>0$), ta có thể đi từ các bậc:

• Bậc $i-1$ (đi 1 bước)
• Bậc $i-2$ (đi 2 bước)
• Bậc $i-3$ (đi 3 bước)

Vậy công thức truy hồi là: $dp[i]=dp[i-1]+dp[i-2]+dp[i-3]$

Chúng ta sẽ tính lần lượt từng bậc:

• $dp[1]=dp[0]=1$
• $dp[2]=dp[1]+dp[0]=1+1=2$
• $dp[3]=dp[2]+dp[1]+dp[0]=2+1+1=4$
• $dp[4]=0$ (bậc 4 hỏng)
• $dp[5]=dp[4]+dp[3]+dp[2]=0+4+2=6$
• $dp[6]=dp[5]+dp[4]+dp[3]=6+0+4=10$
• $dp[7]=dp[6]+dp[5]+dp[4]=10+6+0=16$
• $dp[8]=0$ (bậc 8 hỏng)
• $dp[9]=dp[8]+dp[7]+dp[6]=0+16+10=26$
• $dp[10]=dp[9]+dp[8]+dp[7]=26+0+16=42$
• $dp[11]=dp[10]+dp[9]+dp[8]=42+26+0=68$
• $dp[12]=dp[11]+dp[10]+dp[9]=68+42+26=136$

Vậy có 136 cách để đi hết cầu thang.

Đây là một bài toán quy hoạch động tương tự, nhưng với khả năng đi thêm 4 bậc.

Gọi $dp[i]$ là số cách để đi đến bậc thang thứ $i$.

• $dp[0]=1$ (có 1 cách để bắt đầu ở vị trí xuất phát).
• Các bậc thứ 4 và 8 bị hỏng, do đó $dp[4]=0$ và $dp[8]=0$.

Công thức truy hồi mới sẽ là: $dp[i]=dp[i-1]+dp[i-2]+dp[i-3]+dp[i-4]$

Chúng ta sẽ tính lần lượt từng bậc:

• $dp[1]=dp[0]=1$
• $dp[2]=dp[1]+dp[0]=1+1=2$
• $dp[3]=dp[2]+dp[1]+dp[0]=2+1+1=4$
• $dp[4]=0$ (bậc 4 hỏng)
• $dp[5]=dp[4]+dp[3]+dp[2]+dp[1]=0+4+2+1=7$
• $dp[6]=dp[5]+dp[4]+dp[3]+dp[2]=7+0+4+2=13$
• $dp[7]=dp[6]+dp[5]+dp[4]+dp[3]=13+7+0+4=24$
• $dp[8]=0$ (bậc 8 hỏng)
• $dp[9]=dp[8]+dp[7]+dp[6]+dp[5]=0+24+13+7=44$
• $dp[10]=dp[9]+dp[8]+dp[7]+dp[6]=44+0+24+13=81$
• $dp[11]=dp[10]+dp[9]+dp[8]+dp[7]=81+44+0+24=149$
• $dp[12]=dp[11]+dp[10]+dp[9]+dp[8]=149+81+44+0=274$

Vậy có 274 cách để đi hết cầu thang.