关键在于,将该问题转化为求斐波那契数列的问题,从而利用动态规划来解题。
#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;
}

京公网安备 11010502036488号