LC871. 最低加油次数

LC871-最低加油次数

以次数作为子问题，01动态规划，如果次数的距离可以到达站点i证明是子问题，取出最大距离

func minRefuelStops(target int, startFuel int, stations [][]int) int {
    dp := make([]int, len(stations)+1)
    dp[0] = startFuel

    for i, ss := range stations {
        for j := i; j >= 0; j-- {
            if dp[j] >= ss[0] {
                dp[j+1] = max(dp[j+1], dp[j]+ss[1])
            }
        }
    }

    for i := 0; i < len(dp); i++ {
        if dp[i] >= target {
            return i
        }
    }
    return -1
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}