O(B*N) solution


  • 0
    T
    public class Solution {
        public IList<int> CheapestJump(int[] A, int B) {
            var len = A.Length;
            var dp = new int[len];
            var result = new List<int>();
            if(A[len-1] <0)
                return result;
            dp[len-1] = A[len-1];
            for(int i = len-2;i>=0;i--){
                var v = int.MaxValue;
                if(A[i] < 0)
                {
                    dp[i] = int.MaxValue;
                    continue;
                }
                for(int j = 1;j<=B;j++){
                    if(i+j<len && dp[i+j] != int.MaxValue){
                        v = Math.Min(v,dp[i+j]);
                    }
                }
                if(v != int.MaxValue){
                    dp[i] = v+A[i];
                }else{
                    dp[i] = v;
                }
            }
            
            //Console.WriteLine(string.Join(",",dp));
            int k = 0;
            if(dp[0] != int.MaxValue){
                int current = 0;
                int total = dp[0];
                while(current < len-1){
                    result.Add(current+1);
                    total -= A[current];
                    for(int i = 1;i<=B;i++){
                        if(dp[current+i] == total){
                            current = current+i;
                            break;
                        }
                    }
                }
                result.Add(len);
            }
            return result;
            
        }
    }
    

Log in to reply
 

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