力扣1137题 解题思路和步骤 C++代码实现,力扣一共多少题

一、题目分析

力扣1137题要求我们找到第N个泰波那契数。泰波那契数的定义是：T0 =0, T1 =1, T2 =1, 且在n >= 0的条件下 Tn+3 = Tn + Tn+1 + Tn+2。，当n = 4时，T4 = T3 + T2 + T1 = 4。这道题主要考查我们对递归或动态规划的理解和运用。在思考解题方法时，我们可以考虑从简单的情况入手，逐步推导到一般情况。

二、递归解法思路

递归是一种直观的解法。我们可以直接根据泰波那契数的定义来编写递归函数。当n为0时，返回0；当n为1或2时，返回1。对于n大于2的情况，我们通过递归调用函数自身来计算泰波那契数。即返回泰波那契(n - 1) + 泰波那契(n - 2) + 泰波那契(n - 3)。递归解法存在一个问题，就是会有大量的重复计算。，在计算泰波那契(5)时，泰波那契(3)会被计算多次。递归函数、重复计算、泰波那契数计算、边界条件这些方面需要我们仔细考虑。

三、动态规划解法思路

为了解决递归解法的重复计算问题，我们可以采用动态规划的方法。动态规划通常使用一个数组来保存已经计算过的结果。我们创建一个数组dp，其中dp[i]表示第i个泰波那契数。初始化dp[0] = 0，dp[1] = 1，dp[2] = 1。通过循环从3到n，依次计算dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]。返回dp[n]即可。这种方法避免了重复计算，提高了效率。动态规划数组、初始化、循环计算、效率提升这些要点在动态规划解法中很重要。

四、C++代码实现递归解法

int tribonacci(int n) { 
    if (n == 0) return 0; 
    if (n == 1 || n == 2) return 1; 
    return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3); 
}

五、C++代码实现动态规划解法

int tribonacci(int n) { 
    if (n == 0) return 0; 
    if (n == 1 || n == 2) return 1; 
    vector dp(n + 1); 
    dp[0] = 0; 
    dp[1] = 1; 
    dp[2] = 1; 
    for (int i = 3; i <= n; i++) { 
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; 
    } 
    return dp[n]; 
}