https://www.acmicpc.net/problem/10844
initial
As you have seen in the image, I tried deducing dp pattern with 1d list, something which I should not make it a habit of. When there is a no clear pattern, I should rly consider 2d list for memoisation. So numbers ending with 0 and 9 have only 1 choice - to go 1 from 0 and go to 8 from 9. Other numbers from 2 to 8 can go 1 increment up or 1 increment down so 2 choices. For convenience i tried just multiplying like dp[i][j]=dp[i-1][j]*2 but this is wrong (not sure why tbc)
If we declare 2d dp list where [length of integer][last digit number from 0 to 9]. When n=1, dp[1][0~9] is all 1 and we initialise that as starting point.
solution
n = int(input())
dp = [[0 for _ in range(10)] for _ in range(n + 1)]
for i in range(1, 10):
dp[1][i] = 1
for i in range(2, n+1):
for j in range(10):
if j == 0:
dp[i][j] += dp[i - 1][1]
elif j == 9:
dp[i][j] += dp[i - 1][8]
else:
dp[i][j] += dp[i - 1][j - 1]
dp[i][j] += dp[i - 1][j + 1]
print(sum(dp[n])%1000000000)complexity
n time? cuz j is constant, n space as well if that same logic is correct
yes im right
he time complexity of the provided code is O(n) and the space complexity is O(n).
Time Complexity:
The nested loops iterate over the values of i and j, both ranging from 1 to 9 (for i) and 0 to 9 (for j). This results in O(n) iterations, where n is the input value.
Within the innermost loop, constant time operations are performed.
Space Complexity:
The dp array has dimensions of (n + 1) x 10, resulting in O(n) space complexity.
Other variables used in the code require only constant space.
It's worth noting that the sum(dp[n]) % 1000000000 operation at the end is also performed in constant time, as it sums up a fixed-size list.
