Dynamic Programming approach issue

Alice goes for jogging every day for N meters. Sometimes she runs and sometimes she walks. Her walking speed is 1m/s and running speed is 2m/s . Given the distance up to which she does jogging, calculate the number of ways she can do jogging.

example:

Input: 3 (total distance covered during jogging)

Output: 3 (possible case)

Explanation: Alice could jog in 3 ways

1. Alice Walks for 3 meter
2. Alice Run for 2 meters and then walks for 1 m
3. Alice walks 1m and then run 2m

Example 2:

Input: 4

Output: 5

Explanation: Alice could jog in 5 ways

1. Alice walk for all 4 meters
2. Alice walk for first 2 meters and then run for 2 meters
3. Alice could run for 2 meters and then walk for 2 meters
4. Alice walk for 1 meters and then run for 2 meters and then walk for 1 meters
5. Alice run for all 4 meters

I have solved above problem statement using following code

from itertools import permutations

n = int(input())

c = 0
t = [2]*(n//2)
if n % 2 != 0:
    t = t+[1]

for i in range(t.count(2)):
    c = c+len(set(list(permutations(t, len(t)))))
    t.remove(2)
    t.append(1)
    t.append(1)
c = c+len(set(list(permutations(t, len(t)))))
print(c)

I’m new in dynamic programming, any one can help me ? how i can implement this in dynamic approach method and achieve more optimum time complexivity?

Thankyou very much for giving your valuable towards my problem.

Answer

Inspired by all earlier posts, and the unwritten assumptions being confirmed, this is just another fib-sequence question.

Credits to all earlier posters. (the code is quite simple then) Just for reference – hope it helps.

def jogging_ways(n: int) -> int:
    # f(3) = f(1) + f(2)
    a, b = 1, 1
        
    for i in range(n):
        a, b = b, a+b
        #print(a, b)
        
    return a

Running:

> jogging_ways(4)
  5
> jogging_ways(5) 
  8