时间超限

isdkz

这段代码中存在一个问题，即递归计算lml函数时出现了重复计算，导致时间复杂度过高。可以通过使用动态规划来优化这个问题。

以下是修改后的代码：

1. #include <stdio.h>
   
2. #include <math.h>
   
3. 
   
4. int lml(int n)
   
5. {
   
6.     int dp[n+1];
   
7.     dp[1] = 0;
   
8.     dp[2] = 1;
   
9.     for (int i = 3; i <= n; i++)
   
10.     {
    
11.         dp[ i] = 4 * dp[i-1] - 5 * dp[i-2];
    
12.     }
    
13.     return dp[n];
    
14. }
    
15. 
    
16. int main()
    
17. {
    
18.     int N;
    
19.     scanf("%d", &N);
    
20.     while (N--)
    
21.     {
    
22.         int n;
    
23.         scanf("%d", &n);
    
24.         printf("%d\n", lml(n));
    
25.     }
    
26.     return 0;
    
27. }
    

复制代码

这里使用了一个数组dp来保存中间结果，避免了重复计算，从而降低了时间复杂度。