得到公式f[n] = f[n-1] + f[n-2] + f[n-4];
还要考虑高精度问题。
#include <iostream> using namespace std; int f[1001][1001]={0}; int main(int argc, char const *argv[]) { int n; f[0][1] = 1; f[1][1] = 1; f[2][1] = 2; f[3][1] = 4; for(int i = 4; i < 1001; i++) for(int j = 1; j < 1001; j++) { f[i][j] += f[i-1][j]+f[i-2][j]+f[i-4][j]; f[i][j+1] += f[i][j]/10; f[i][j] %= 10; } while(cin >> n) { int k = 1001; while(!f[n][k--]); cout << f[n][k+1]; for(k; k > 0; k--) cout << f[n][k]; cout << endl; } return 0; }