动态规划方法问题

Question

爱丽丝每天慢跑N米。有时她运行s 有时她走路。她的步行速度是 1m/s 而运行ning 速度是 2m/s 。给定她慢跑的距离，计算她可以慢跑的方式数。

示例：

输入：3（慢跑的总距离）

输出：3（可能的情况）

说明：爱丽丝可以用 3 种方式慢跑

爱丽丝步行 3 米
Alice 运行走 2 米，然后走 1 米
Alice 走了 1m，然后运行2m

示例 2：

输入：4

输出：5

解释：爱丽丝可以用 5 种方式慢跑

爱丽丝步行 4 米
爱丽丝先走 2 米，然后运行走 2 米
爱丽丝可以运行走2米然后走2米
Alice 走 1 米然后运行走 2 米然后走 1 米
爱丽丝运行全部4米

我已经使用下面的代码解决了上面的问题陈述


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)

我是动态规划的新手，有人可以帮助我吗？我如何在动态方法中实现这一点并实现更优化的时间复杂度？

非常感谢您对我的问题给予的宝贵意见。

Answer 1

受所有早期帖子的启发，并确认了不成文的假设，这只是另一个 fib-sequence 问题。

感谢所有早期发帖人。（那么代码就很简单了）仅供参考，希望对你有帮助。

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

运行:

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

动态规划方法问题

Dynamic Programming approach issue

python

combinations

dynamic-programming

permutation