p114.py 1.08 KB
Newer Older
1 2
# 
# Solution to Project Euler problem 114
3
# Copyright (c) Project Nayuki. All rights reserved.
4
# 
5
# https://www.nayuki.io/page/project-euler-solutions
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
# https://github.com/nayuki/Project-Euler-solutions
# 


	
# How many ways can a row n units long be filled? Denote this quantity as ways[n].
# Compute n = 0, 1, 2 manually as base cases.
# 
# Now assume n >= 3. Look at the leftmost item and sum up the possibilities.
# - If the item is a black square, then the rest of the row is allowed
#   to be anything of length n-1. Add ways[n-1].
# - If the item is a red block with length k where k >= 3, then:
#   - If k = n, then the whole row is filled by this red block. Add 1.
#   - Otherwise k < n, this red block is followed by a black square, then followed
#     by anything of length n-k-1. So add ways[n-4] + ways[n-5] + ... + ways[0].
def compute():
	# Dynamic programming
	LENGTH = 50
	ways = [0] * (LENGTH + 1)
	for n in range(len(ways)):
		if n < 3:
			ways[n] = 1
		else:
			ways[n] = ways[n - 1] + sum(ways[ : n - 3]) + 1
	return str(ways[-1])


if __name__ == "__main__":
	print(compute())