Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
branch & bound with stack solution in Speedy category for Staircase by juestr
def staircase(digits: str) -> int:
def add_digit():
s = prefix + digits[idx]
i = int(s)
if i > last:
return count + 1, idx + 1, i, ""
else:
return count, idx + 1, last, s
def skip_digit():
return count, idx + 1, last, prefix
def h():
return count + (N - idx + len(prefix)) // len(str(abs(last)))
N = len(digits)
best = 0
stack = [(0, 0, -1, "")]
while stack:
count, idx, last, prefix = stack.pop()
best = max(best, count)
if idx < N and h() > best:
stack.append(skip_digit())
stack.append(add_digit())
return best
Aug. 9, 2023
Comments:
