类似于斐波切数列，自下而上，添加备忘
1 #include <iostream> 2 #include <queue> 3 #include <climits> 4 #include <algorithm> 5 #include <memory.h> 6 #include <stdio.h> 7 #include <ostream> 8 #include <vector> 9 #include <list> 10 #include <cmath> 11 #include <string> 12 #include <stdexcept> 13 #include <stack> 14 using namespace std; 15 16 int dp[1000]; 17 18 //dp的核心是空间换时间，加备忘录是一个不错的选择 19 void fun(int n) 20 { 21 dp[1] = 1; 22 dp[2] = 2; 23 dp[3] = 4; 24 int i; 25 for(i = 1; i <= n ; ++i) 26 { 27 dp[n] = dp[n-1]+dp[n-2]+dp[n-3]; 28 } 29 return; 30 } 31 32 int main() 33 { 34 int n; 35 cin>>n; 36 fun(n); 37 cout<<dp[n]; 38 return 0; 39 }