关键在于,将该问题转化为求斐波那契数列的问题,从而利用动态规划来解题。
#include <iostream> #include <vector> using namespace std; // 求斐波那契数列 int main(){ int n = 0; cin >> n; // 1 确定dp数组及其下标的含义:dp[i]表示第i个月的兔子总数 vector<int> dp(n + 1, 0); // 2 确定递归公式:dp[i] = dp[i-1] + dp[i-2] // 3 初始化dp数组 dp[0] = 0; dp[1] = 1; // 4 确定递归顺序,从前往后 for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } cout << dp[n] << endl; }