10.16 腾讯笔试求解

知道是海笔全当练手，然而最难受的是练完手看不到正解QAQ

求问下题AC思路：

原题描述：

小Q来到了一个级台阶前。已知小Q的左脚每次可以迈奇数级台阶，右脚每次可以迈偶数级台阶（不能是0）他准备用左、右***替的方式进行跳台阶：即除了第一步可以
随意选择以外，后面的每一步的奇偶性一定和前一步不同。小Q想知道，自己跳上这阶台阶，共有多少种不同的方式？

TLE代码(72%)：

    def func5(self):
        n = int(input())
        dp = [[0] * (2) for _ in range(n+1)]
        dp[1][0], dp[1][1] = 1, 0
        dp[2][0], dp[2][1] = 0, 1
        for i in range(3, n+1):
            for j in range(1, i):
                if((i-j) % 2 == 1):
                    dp[i][0] += dp[j][1]
                else:
                    dp[i][1] += dp[j][0]
            if i % 2 == 0:
                dp[i][1] += 1
            else: dp[i][0] += 1
        print(sum(dp[n]))
        return