Initial approach
I first tried finding the pattern
1
= 1
1 way
2
= 1 1
= 2
2 ways
3
= 1 1 1
= 1 2
= 2 1
= 3
4 ways
4
= 1111
= 211
= 121
= 112
= 22
= 13
= 31
7 ways
5 = 13 ways ( i only thought of 11 ways excluding 32 and 23)
So the pattern, which I couldn't find out becaue my dp[5] was wrong, is dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
This is similar to min. steps taken to reach a floor Leetcode question and Fibonnai sequence. But how does this pattern actually work?
Model solution
Lets look when i=4.
1) at i=1, dp[1] represents the total number of ways to represent 1, which is 1. We can add a 3 to it to reach 4.
2) at i=2, dp[2] is 2, which is 11 and 2. We can add a 2 to it to reach 4.
3) at i=3, dp[2] is 4 ways, which is 12, 111, 21, 3. We can just add a 1 to it to reach 4.
So this is like the minimum number of steps in Leetcode where it is like dp[3] + 1, dp[2] + 2 and dp[1] + 3 to reach dp[4]. (by adding +1/2/3, I mean given previous steps of dp[1] to dp[3] and having the options to add 1/2/3 by the question, we can calculate dp[4], the total ways to reach 4)
n = int(input())
lst = [] # Initialize the list to store input values
for _ in range(n):
lst.append(int(input())) # Read and store the input values
dp = [0] * 11 # Initialize the dp array with 11 elements, initially all zeros
dp[1] = 1
dp[2] = 2
dp[3] = 4
for i in range(4, 11):
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
for num in lst:
print(dp[num])complexity
The time complexity of your code is O(n) because you have a loop that iterates through the lst list of input values, and the number of iterations in this loop is determined by the value of n.
The space complexity is O(1) because you use a fixed-size dp array with a constant number of elements (11 in this case), and the size of the lst list also does not depend on the input size.
So, in terms of time and space complexity, your code is efficient and runs in linear time with constant space usage.
