Expert · Dynamic programming · 220 of 264
Word break
Can the text be split into words that are all in the dictionary (words may be used more than once)?
Input: the dictionary words on one line, then the text. Output: yes or no
Examples
Input
apple pen applepen pine pineapple pineapplepenapple
Output
yes
Input
cats dog sand and cat catsandog
Output
no
Input
a aa aaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
Output
yes
One more test checks other inputs when you press Check.
Stuck? The idea behind dynamic programming
Break the problem into smaller ones that repeat, and keep each answer in a table so it is worked out only once.
Decide what one cell of the table means ("the best total using the first i items"), how it follows from earlier cells, and where it starts.
n = 10
ways = [0] * (n + 1)
ways[0] = 1
for i in range(1, n + 1):
ways[i] = ways[i - 1] + (ways[i - 2] if i >= 2 else 0)
print(ways[n]) # climbing 10 stairs, 1 or 2 at a timeWatch for: Fill the table in an order where every cell it needs is already filled.