欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

dp,洛谷p1028 数的计算

程序员文章站 2022-07-13 11:58:57
...

dp,洛谷p1028 数的计算

#include<iostream>
using namespace std;


long long dp[1005] = { 0 };
int main()
{
	int n;
	cin >> n;
	dp[0] = 1;
	dp[1] = 1;
	dp[2] = 2;
	//这是找规律看出来的
	for (int i = 3; i <= n; i++){
		dp[i] = dp[i - 2] + dp[i / 2];
	}
	cout << dp[n];
	//正常的思路,例如6 
	//6前面一位是0不处理,前面一位是1,16,前面一个是2,有两种126,26,前面一位是3,有两种136,36
	for (int i = 3; i <= n; i++){
		for (int j = 0; j <= n / 2; j++){
			dp[i] += dp[j];
		}
	}
}
相关标签: dp 算法