Đếm số cách nhảy để đến cuối mảng trong C++

Cho một mảng các số dương. Mỗi phần tử đại diện cho số lượng nhảy tối đa có thể thực hiện từ chỉ số đó để đến cuối mảng. Mục tiêu là tìm số lượng cách nhảy từ phần tử đó để đến cuối mảng. Nếu arr[] là [1,2,3] thì đối với 1 có thể nhảy 1, đối với 2 có thể nhảy 1 hoặc 2 và đối với 3 có thể nhảy 1, 2 hoặc 3.

Ví dụ

Đầu vào

arr[] = {1,2,3}

Đầu ra

Số cách nhảy để đến cuối mảng là: 1 1 0

Giải thích

Đối với 1, các nhảy: 1. Đối với 2, các nhảy 1 hoặc 2, để đến cuối chỉ cần một nhảy 1. Đối với 3, các nhảy 1,2 hoặc 3, vì ở cuối không cần nhảy.

Đầu vào

arr[] = {4,3,6,2}

Đầu ra

Số cách nhảy để đến cuối mảng là: 4 2 1 0

Giải thích

Đối với 4, các nhảy: 1, 2, 3 hoặc 4. Để đến cuối cần 1,2 hoặc 3. Các cách: 4-3-6-2, 4-6-2, 4-2, 4-3-2. Tổng 4. Đối với 3, nhảy 1, 2 hoặc 3 để đến cuối cần cả hai. Cách: 3-6-2, 3-2. Tổng 2. Đối với 6, nhảy 1 đến 5, đến cuối cần 1. Cách: 6-2. Tổng 1. Đối với 2, nhảy 1 hoặc 2, vì ở cuối không cần nhảy.

Phương pháp sử dụng

Trong phương pháp này, đối với mỗi phần tử arr[i] chúng ta sẽ cộng số cách đến cuối mảng cho tất cả các phần tử phía trước arr[i] và có thể đến được từ phần tử hiện tại. Cộng thêm 1 vào số cách này cho arr[i] nếu chúng ta có thể trực tiếp đến cuối từ arr[i] trong một nhảy duy nhất.

Nhận mảng nguyên arr[].
Hàm reach_end(int arr[], int size) nhận mảng và trả về số cách nhảy để đến cuối.
Tạo mảng arr_2[] để lưu số cách đến cuối từ mỗi phần tử của arr[].
Khởi tạo toàn bộ arr_2[] bằng 0 sử dụng memset(arr_2, 0, sizeof(arr_2)).
Duyệt arr[] bằng vòng lặp for từ i=size-2 đến i=0, vì phần tử cuối cùng sẽ không được xem xét.
Lấy temp = size - i - 1. Nếu temp >= arr[i] thì chúng ta có thể trực tiếp đến cuối bằng một nhảy. Tăng số cách cho arr[i] bằng arr_2[i]++.
Bây giờ đối với tất cả các phần tử khác có thể đến cuối và mà chúng ta có thể đến từ arr[i], cộng số cách vào arr_2[i].
Để làm điều trên, duyệt bằng vòng lặp for từ j=i+1 đến j<size-1 và j<=arr[i]+i. Nếu bất kỳ arr[j] không phải -1, cộng nó vào arr_2[i].
Nếu arr_2[i] vẫn là 0 thì đặt nó thành -1, có nghĩa là không thể đến cuối.
Cuối cùng của tất cả vòng lặp, chúng ta sẽ có arr_2[] chứa số cách đến cuối cho mỗi phần tử của arr[].
In arr_2 bằng vòng lặp for làm kết quả.

Ví dụ mã

#include <bits/stdc++.h> 
using namespace std; 

void reach_end(int arr[], int size) {
    int arr_2[size];
    memset(arr_2, 0, sizeof(arr_2));
    
    for (int i = size-2; i >= 0; i--) {
        int temp = size - i - 1;
        if (arr[i] >= temp) {
            arr_2[i]++;
        }
        
        for (int j = i+1; j < size-1 && j <= arr[i] + i; j++) {
            if (arr_2[j] != -1) {
                arr_2[i] = arr_2[i] + arr_2[j];
            }
        }
        
        if (arr_2[i] == 0) {
            arr_2[i] = -1;
        }
    }
    
    cout << "Số cách nhảy để đến cuối mảng là: ";
    for (int i=0; i < size; i++) {
        cout << arr_2[i] << " ";
    }
}

int main() {
    int arr[] = {2, 3, 7, 1, 8, 9};
    int size = sizeof(arr) / sizeof(arr[0]);
    reach_end(arr, size);
    return 0;
}

Đầu ra

Nếu chạy mã trên, sẽ tạo ra đầu ra sau:

Số cách nhảy để đến cuối mảng là: 8 5 3 1 1 0