Quy hoạch động - bài VSTEPS SPOJ

VSTEPS là một bài tập Quy hoạch động cơ bản, phù hợp cho các bạn luyện tập tư duy ở giai đoạn đầu khi đang làm quen với mô hình thiết kế thuật toán Quy hoạch động. 

Như mình đã chia sẻ các bước suy nghĩ để xây dựng thuật toán Quy hoạch động cho một bài toán theo trình tự các bước, dưới đây là vận dụng phương pháp vào bài VSTEPS - SPOJ.

Đề bài VSTEPS được tóm tắt như sau: Một cầu thang N bậc được đánh số từ 1 tới N. Lucky có thể đi lên 1 hoặc 2 bậc. Tuy nhiên một số bậc thang bị hỏng và không thể bước chân lên được. Bậc thang 1 luôn không thủng và là vị trí đứng ban đầu của Lucky. Hỏi có bao nhiêu cách để Lucky leo hết được cầu thang?

1. Định nghĩa hàm Quy hoạch động: bài toán yêu cầu tìm số cách để leo được lên bậc thứ N, như vậy ta gọi F(n) là số cách tới được bậc thang thứ N. Số cách này chỉ phụ thuộc vào N mà thôi.
2. Tìm công thức Quy hoạch động: Ta giả sử đang đứng ở bậc thứ i, khi đó có hai trường hợp:
• Nếu bậc thứ i bị thủng --> Không có cách nào tới được bậc i đó -> F(i)=0
• Nếu bậc thứ i không bị thủng --> số cách tới được bậc i là F(i)=F(i-1)+F(i-2) vì Lucky chỉ có thể nhảy từ bậc (i-1) lên hoặc từ bậc (i-2) lên mà thôi
3. Tìm cơ sở quy hoạch động: Tại vị trí đầu tiên, Lucky đứng tại chỗ, như vậy có 1 cách: F(1)=1; Ta có thể xem trước bậc 1 là bậc 0, coi như bậc hỏng và ta có F(0)=0.
4. Lập bảng phương án: ta lưu các giá trị F(i) vào mảng 1 chiều; Ban đầu có F[0]=0; F[1]=1; ta tính F[2]=0 nếu bậc 2 là bậc hỏng; F[2]=F[0]+F[1]=0+1=1; tương tự thế ta tính lần lượt các F[i] với i từ 3 tới N.
5. Kết quả cần tìm sẽ chính là F[n]: số cách khác nhau để tới được bậc N
6. Cách code để tính F[i]: 
       for(int i=3; i<=n; i++){
           if(a[i]==0){
               F[i]=0;
           }
           else{
               F[i]=F[i-1]+F[i-2];
           }
       }
       cout << F[n];