From N! to N^2 (Dynamic Programming)

Here is the problem: https://leetcode.com/problems/jump-game/

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.

Normally this would be an N! solution: for each element i you can try i-1 permutations for a total of N*(N-1)*(N-2)*....*1 = N!.
Using DP you can optimize this significantly, from exponential to polynomial. Assume that you have the solution for all indexes 0, 1, 2, ...., N-1. Hence the solution for N will follow the following rule:
 - Go to all previous solutions, check if you can get to N from each one
 - If so, the solution for N will be Min(current solution for N, solution(i) + 1)

However, the reality is that it did not pass the LeetCode test... :( Two test cases failed, and I had to come up with few "special cases", which I'm not super proud of. Well, sometimes (most of the times) in life the solutions to your problems will be 97% pretty, with a nasty but necessary 3%... Cheers, ACC.

public class Solution
{
    public int Jump(int[] nums)
    {
        int[] dp = new int[nums.Length];

        //Hack Begins
        bool allOne = true;
        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] != 1)
            {
                allOne = false;
                break;
            }
        }
        if (allOne) return nums.Length - 1;
        if (nums.Length == 1) return 0;
        if (nums[0] >= nums.Length) return 1;
        //Hack Ends

        dp[0] = 0;
        for (int i = 1; i < nums.Length; i++)
        {
            dp[i] = Int32.MaxValue;
            for (int j = 0; j < i; j++)
            {
                if (nums[j] >= i - j && dp[j] + 1 < dp[i])
                {
                    dp[i] = dp[j] + 1;
                }
                if (dp[i] == 1) break;
            }
        }

        return dp[dp.Length - 1];
    }
}