golang solution


  • 0
    C
    import "math"
    
    func cheapestJump(A []int, B int) []int {
        var res []int
        sum := make([]int, len(A))
        next := make([]int, len(A))
        for i := range sum {
            sum[i] = math.MaxInt32
            next[i] = -1
        }
        N := len(A)
        
        if A[N-1] == -1 {
            return res
        }    
        sum[N-1] = A[N-1]
        next[N-1] = -1
        
        for i := N-2; i >= 0; i-- {
            if A[i] == -1 {
                sum[i] = math.MaxInt32
                next[i] = -1
                continue
            }
            for j := i+1; j <= i+B && j < N; j++ {
                if sum[j] < math.MaxInt32 && sum[j] + A[i] < sum[i] {
                    sum[i] = sum[j] + A[i]
                    next[i] = j
                }
            }
        }
        
        if sum[0] == math.MaxInt32{
            return res
        }
        
        for i:=0; i != -1; {
            res = append(res, i+1)
            i = next[i]
        }
         
        return res
    }
    

Log in to reply
 

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