מריה בוטוסוב

נותנים מערך של קפיצות. יש להחזיר מספר קפיצות מינימלי שמאפשר להגיעה לסוף המערך. לדוגמה: 3, 4, 2, 1, 2, 3, 7, 1, 1, 1, 3 מספר קפיצות: 4

//dynamic programming (less optimal solution) O(N^2)
public static int MinimumNumberOfJumps(int[] array) {
    int[] jumps = new int[array.Length];
    Array.Fill(jumps, Int32.MaxValue);
    jumps[0] = 0;
    for(int i = 1; i < array.Length; i++) {
        for(int j = 0; j < i; j++) {
            if(array[j] >= i - j)
                jumps[i] = Math.Min(jumps[j] + 1, jumps[i]);
        }
    }
    return jumps[jumps.Length - 1];
}
 
//more optimal solution O(N) time
public static int MinimumNumberOfJumps(int[] array) {
    if(array.Length == 1)
        return 0;
    int jumps = 0;
    int maxReach = array[0];
    int steps = array[0];
    for(int i = 1; i < array.Length - 1; i++) {
        maxReach = Math.Max(maxReach, i + array[i]);
        steps--;
        if(steps == 0) {
            jumps++;
            steps = maxReach - i;
        }
    }
    return jumps + 1;
}