C# implementation with DP


  • 0
    G
        bool CanCross(int[] stones)
        {
            // Trivial case
            if (stones.Length == 1) return true;
            // Dictionary to keep track of computed values for each stone and jump value (k) 
            Dictionary<Tuple<int, int>, bool> store = new Dictionary<Tuple<int, int>, bool>();
           
            return CanCross(stones, 0, 0, store);
        }
    
        bool CanCross(int[] stones, int start, int lastJump, Dictionary<Tuple<int, int>, bool> store)
        {
            int end = stones.Length - 1;
    
            // base cases
            if (stones[end] - stones[start] == lastJump - 1 || 
                stones[end] - stones[start] == lastJump || 
                stones[end] - stones[start] == lastJump + 1) return true;
    
            Tuple<int, int> key;
            int step = 0; // index of next step, if exists
    
            // case: k-1
            if (lastJump > 1)
            {
                // Get to the next stone by adding (k-1), where k is last jump value.
                step = Array.IndexOf(stones, stones[start] + (lastJump - 1));
                if (step > 0 && step <= end)
                {
                    // If you can get to the next stone, and can legally reach to the end from there, return true.
                    key = new Tuple<int, int>(lastJump - 1, step);
                    if (!store.ContainsKey(key)) { store[key] = CanCross(stones, step, (lastJump - 1), store); }
                    if (store[key]) return true;
                }
            }
    
            // case: k
            if (lastJump > 0)
            {
                // If you could not get to the next stone by jumping k-1, try k; recurse with the same logic as above.
                step = Array.IndexOf(stones, stones[start] + lastJump);
                if (step > 0 && step <= end)
                {
                    key = new Tuple<int, int>(lastJump, step);
                    if (!store.ContainsKey(key)) { store[key] = CanCross(stones, step, lastJump, store); }
                    if (store[key]) return true;
                }
            }
    
            // case: k+1
            if (lastJump >= 0)
            {
                // Finally, try jumping k+1; recurse with the same logic as above.
                step = Array.IndexOf(stones, stones[start] + (lastJump + 1));
                if (step > 0 && step <= end)
                {
                    key = new Tuple<int, int>(lastJump + 1, step);
                    if (!store.ContainsKey(key)) { store[key] = CanCross(stones, step, lastJump + 1, store); }
                    if (store[key]) return true;
                }
            }
    
            // If you cannot get to the next stone with, k-1, k, or k+1 jump, return false.
            return false;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.