首页#include<math.h> #include<algorithm> #include<iostream> #include<string.h> #define ll long long #define endl "\n" using namespace std; typedef pair<int, int>pll; const int N = 2e5 + 10; pll c[N]; int h[150][150]; int x[N], y[N], dp[5055][5055], ss[N]; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } ll a[N]; int n; signed main() { int n; cin >> n; dp[1][1] = 1, dp[2][1] = 2; int right = 1; for (int i = 3; i <= n; i++) { for (int j = 1; j <= right; j++) { dp[i][j] = dp[i - 1][j] + dp[i - 2][j]; } for (int j = 1; j <= right; j++) { if (dp[i][j] >= 10) { dp[i][j + 1] += dp[i][j] / 10; dp[i][j] %= 10; if (dp[i][right + 1])right++; } } } for (int i = right; i >= 1; i--) { cout << dp[n][i] ; } return 0; }

#include<math.h> #include<algorithm> #include<iostream> #include<string.h> #define ll long long #define endl "\n" using namespace std; typedef pair<int, int>pll; const int N = 2e5 + 10; pll c[N]; int h[150][150]; int x[N], y[N], dp[5055][5055], ss[N]; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } ll a[N]; int n; signed main() { int n; cin >> n; dp[1][1] = 1, dp[2][1] = 2; int right = 1; for (int i = 3; i <= n; i++) { for (int j = 1; j <= right; j++) { dp[i][j] = dp[i - 1][j] + dp[i - 2][j]; } for (int j = 1; j <= right; j++) { if (dp[i][j] >= 10) { dp[i][j + 1] += dp[i][j] / 10; dp[i][j] %= 10; if (dp[i][right + 1])right++; } } } for (int i = right; i >= 1; i--) { cout << dp[n][i] ; } return 0; }

时间: 2023-12-20 20:06:01 浏览: 100

这段代码是一个计算斐波那契数列的程序，通过动态规划的方式计算斐波那契数列的第n项的值。首先，程序从输入中获取一个整数n，表示要计算的斐波那契数列的项数。然后，程序初始化dp数组，其中dp[i][j]表示斐波那契数列第i项的第j位数字。初始时，dp[1][1]为1，dp[2][1]为2。接下来，程序通过循环计算dp数组的其他项。对于每个i大于等于3的值，程序通过将前两项的对应位相加得到当前项的值。同时，如果当前位的值大于等于10，就需要进位到下一位。最后，程序从右往左输出dp数组中第n项的值。注意，在这段代码中，会存在数组越界的问题。例如，当n=1时，dp[n][i]中的i可能会超出数组的范围。

阅读全文