Cách tìm số nhảy tối thiểu để đến cuối mảng bằng C#

Chúng ta có thể bắt đầu từ phần tử đầu tiên và đệ quy gọi cho tất cả các phần tử có thể đạt được từ phần tử đầu. Số nhảy tối thiểu đến cuối từ đầu có thể tính bằng số nhảy tối thiểu từ các phần tử đạt được từ đầu.

Mảng: {1, 3, 6, 3, 2, 3, 6, 8, 9, 5}

Số bước cần thiết: 4

Ví dụ

using System;

namespace ConsoleApplication
{
    public class Arrays
    {
        public int MinJumps(int[] arr, int l, int h)
        {
            if (h == l)
                return 0;
            if (arr[l] == 0)
                return int.MaxValue;
            int min = int.MaxValue;
            for (int i = l + 1; i <= h && i <= l + arr[l]; i++)
            {
                int jumps = MinJumps(arr, i, h);
                if (jumps != int.MaxValue && jumps + 1 < min)
                    min = jumps + 1;
            }
            return min;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Arrays a = new Arrays();
            int[] arrm = { 1, 3, 6, 3, 2, 3, 6, 8, 9, 5 };
            int n = arrm.Length;
            Console.Write(" Minimum number of jumps to reach end is " + a.MinJumps(arrm, 0, n - 1));
        }
    }
}

Kết quả

4

Giải thích: Đệ quy tìm số nhảy tối thiểu. Từ vị trí i có thể nhảy tối đa arr[i] bước. Thử tất cả vị trí có thể đến, lấy min. Cảnh báo: giải pháp đệ quy này O(n^2) và có thể stack overflow. Nên dùng DP hoặc Greedy O(n) cho mảng lớn.