Dynamic programming is a strategy for developing an algorithm where each subproblem is solved and the results recorded for use in solving larger problems. In this exercise you will write a pair of dynamic programming methods.

Newman-Conway sequence is the one which generates the following integer sequence. 1 1 2 2 3 4 4 4 5 6 7 7….. and follows below recursive formula.

P(1) = 1
P(2) = 1
for all n > 2
P(n) = P(P(n - 1)) + P(n - P(n - 1))

Note: if the input is 0 or less, a ValueError is raised.

Given a number n then print n terms of Newman-Conway Sequence

Examples:

Input : 0
Output: ValueError

Input : 1
Output: 1

Input : 2
Output : 1 1

Input : 4
Output : 1 1 2 2

Input : 13
Output : 1 1 2 2 3 4 4 4 5 6 7 7 8

Input : 20
Output : 1 1 2 2 3 4 4 4 5 6 7 7 8 8 8 8 9 10 11 12

You should be able to do this in O(n) time complexity.

• GeeksforGeeks: Newman-Conway Sequence