<p>You are given an integer <code>hoursBefore</code>, the number of hours you have to travel to your meeting. To arrive at your meeting, you have to travel through <code>n</code> roads. The road lengths are given as an integer array <code>dist</code> of length <code>n</code>, where <code>dist[i]</code> describes the length of the <code>i<sup>th</sup></code> road in <strong>kilometers</strong>. In addition, you are given an integer <code>speed</code>, which is the speed (in <strong>km/h</strong>) you will travel at.</p>

<p>After you travel road <code>i</code>, you must rest and wait for the <strong>next integer hour</strong> before you can begin traveling on the next road. Note that you do not have to rest after traveling the last road because you are already at the meeting.</p>

<ul>
	<li>For example, if traveling a road takes <code>1.4</code> hours, you must wait until the <code>2</code> hour mark before traveling the next road. If traveling a road takes exactly&nbsp;<code>2</code>&nbsp;hours, you do not need to wait.</li>
</ul>

<p>However, you are allowed to <strong>skip</strong> some rests to be able to arrive on time, meaning you do not need to wait for the next integer hour. Note that this means you may finish traveling future roads at different hour marks.</p>

<ul>
	<li>For example, suppose traveling the first road takes <code>1.4</code> hours and traveling the second road takes <code>0.6</code> hours. Skipping the rest after the first road will mean you finish traveling the second road right at the <code>2</code> hour mark, letting you start traveling the third road immediately.</li>
</ul>

<p>Return <em>the <strong>minimum number of skips required</strong> to arrive at the meeting on time, or</em> <code>-1</code><em> if it is<strong> impossible</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> dist = [1,3,2], speed = 4, hoursBefore = 2
<strong>Output:</strong> 1
<strong>Explanation:</strong>
Without skipping any rests, you will arrive in (1/4 + 3/4) + (3/4 + 1/4) + (2/4) = 2.5 hours.
You can skip the first rest to arrive in ((1/4 + <u>0</u>) + (3/4 + 0)) + (2/4) = 1.5 hours.
Note that the second rest is shortened because you finish traveling the second road at an integer hour due to skipping the first rest.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> dist = [7,3,5,5], speed = 2, hoursBefore = 10
<strong>Output:</strong> 2
<strong>Explanation:</strong>
Without skipping any rests, you will arrive in (7/2 + 1/2) + (3/2 + 1/2) + (5/2 + 1/2) + (5/2) = 11.5 hours.
You can skip the first and third rest to arrive in ((7/2 + <u>0</u>) + (3/2 + 0)) + ((5/2 + <u>0</u>) + (5/2)) = 10 hours.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> dist = [7,3,5,5], speed = 1, hoursBefore = 10
<strong>Output:</strong> -1
<strong>Explanation:</strong> It is impossible to arrive at the meeting on time even if you skip all the rests.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == dist.length</code></li>
	<li><code>1 &lt;= n &lt;= 1000</code></li>
	<li><code>1 &lt;= dist[i] &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= speed &lt;= 10<sup>6</sup></code></li>
	<li><code>1 &lt;= hoursBefore &lt;= 10<sup>7</sup></code></li>
</ul>

class Solution:
    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:
        # default case:
            # sum(ceil(d/s)) -> if < hoursBefore, good
            # sum(d/s) -> if > hoursBefore, -1
        # dp?
            # need to try skipping any combination of rests
                # 2**1000
            # cur can be either a float or ceil'd
                # but might be like 2**1000 possible floats
                # eg 1+2,
                    # ceil(1)+2
                        # ceil(ceil(1)+2)
                            # 1.5 + 2.1
                                # vs ceil(1.5)+2.1
                                # will be the same unless (1-fraci)+fracj > 1
                                    # e.g. 1.1 + 2.9
                    # or ceil(1+2)
                        # once we take a rest we consolidate all prev rests
            # what's the wasted work?
                # some float values make no difference
                    # eg 1.1 vs 1.2 -> only makes a diff if frac(d)+frac(cur) > 1
                    # could potentially just test +- 1?
                        # but fracs can eventually sum to >1?
                    # could check just floor and ceil, but some answers will be wrong
                    # if floor, test at the end if they add up?
                        # ie, look at the floors, then decide at the end how many of them we actually needed?
            # dp(i, cur)
        # dist = [d/speed for d in dist]
        # or could we divide by speed at the end?
            # sum(ceil(d/speed)) = (d + (-d % speed)) / speed
            # so at each pass, looking at cursum vs cursum + (-cursum%speed)
                # cursum + (-cursum%speed) -> m*speed
                    # (speed-cursum)% speed -> (speed-lastsum)%speed + (-d%speed)
            # floor: (d - (d%speed))/speed
            # ceil: (d + (-d%speed))/speed
        # convert to km(?)
        hoursBefore *= speed
        skips = [0]
        ceils = [0]
        for d in dist:
            skips.append(skips[-1] + d)
            ceils.append(ceils[-1] + d + (-d % speed))
        s = set()
        m = defaultdict(list)
        if skips[-1] > hoursBefore:
            return -1
        if ceils[-1] <= hoursBefore:
            return 0
        # print(skips)
        # print(ceils)

        @lru_cache(None)
        # n, ~2, n
        # cur is an int
            # if skipstart != -1:
                # cur is sum
        # still have too many curs
            # by the end, have 13k+ curs for the end idx
            # at any given point:
                # have ceil(some_num) + cur_skips
                # or
                    # ceil(stopping_point) + ceil(cur_ceil'd)
                # can reduce it a bit by tracking both ceilstart and skipstart
                    # then only have to consoldiate a value when double switch
                        # eg ceil,skip,ceil
                    # what if we don't pass cur?
                        # just calc it at the end?
                        # so func returns numskips, val
                            # but there are multiple values, depending on the skips...
                            # so it might have to store full map of skips: min(val)
                            # there are n-i possible skips, so each recursion would store n vals
                            # each recursion also does n work
                                # dp in that case is just rec(i) I think
                                # so 1000*1000...
                    # dp is then:
                        # rec(i) = what's the best value I can get for each # of skips
                        # rec(0) = {0: ceil(v), 1: v}
                        # rec(1) = {0: ceil(0)+ceil(1), 1: min(ceil(0+1), 0+ceil(1), 2: 0+1)}

        def rec(i):
            if i < 0:
                # no array means val of 0
                return {0: 0}
            me = dist[i]
            d = rec(i-1)
            new_d = {}
            for nskips, v in d.items():
                ceil_me = v + me
                ceil_me += (-ceil_me % speed)
                if nskips not in new_d or ceil_me < new_d[nskips]:
                    new_d[nskips] = ceil_me
                skip_me = v+me
#                if skip_me < new_d[nskips+1]:
                new_d[nskips+1] = skip_me
            # print(i, new_d)

            return new_d

            # s.add((i, cur, skipstart))
            # m[i].append(cur)
            if len(s) > 10000000:
                return -1
            if cur > hoursBefore:
                return -1
            if i >= len(dist):
                if skip:
                    fullcur = cur + skips[i] - skips[skipstart]
                    # if fullcur < hoursBefore+1:
                        # print('end', fullcur)
                else:
                    fullcur = cur + ceils[i] - ceils[skipstart]
                # print('end', cur, fullcur, fullcur/speed, skip, skipstart)

                if fullcur > hoursBefore:
                    return -1
                # else:
                    # if cur < hoursBefore+1:
                        # print('end', cur)
                return 0
            # need to return full {skips: min(v)}
                # also need to store values based on whether cur did or didn't skip itself
                    # if I did skip, val is me + next
                    # if I didn't skip, val is 
                # at the end, just have 0: 0
                # last element: 0: ceil(elem), 1: elem
                # 2nd to last:
                    # skip:
                        # call rec(i+1, skip=False)
                        # 1: ceil(skip+elem)
                        # 2: skip+elem
                    # noskip:
                        # 0: ceil(skip) + ceil(elem)
                        # 1: ceil(skip) + elem
                # if we ceil ourselves, 
            ret = {}



            fullcur = cur            
            # if skipstart != -1:
            if skip:
                fullcur += skips[i] - skips[skipstart] + dist[i]
                # if we're ending the skip, need to calc the ceil now
                ccur = fullcur + (-fullcur % speed)
                next = rec(i+1, ccur, i+1, False)
            else:
                fullcur += ceils[i] - ceils[skipstart]
                next = rec(i+1, cur, skipstart, False)
            # ccur = fullcur + (-fullcur % speed)
            # next = rec(i+1, ccur, -1)
            if next != -1:
                best = next
            if True:#ccur != fullcur:
                if skip:
                    pass
                else:
                    skipstart = i
                    # if we started a skip, need to lock in the ceil'd value
                    cur = fullcur
                # print('startskip', i, cur, skipstart)
                next = rec(i+1, cur, skipstart, True)
                if next != -1 and (best == -1 or 1+next < best):
                    best = 1+next
            return best

        # ret = rec(0, 0, 0)
        # s2 = sorted([(len(v), i) for i, v in m.items()],reverse=True)
        # print(s2)
        ret = rec(len(dist)-1)
        # print(ret)
        best = math.inf
        for skips, v in ret.items():
            if v > hoursBefore:
                continue
            best = min(best, skips)
        if best == math.inf:
            return -1
        return best

419