首页 > ACM题库 > HDU-杭电 > hdu 2154 跳舞毯-动态规划-[解题报告]C++
2013
12-30

hdu 2154 跳舞毯-动态规划-[解题报告]C++

跳舞毯

问题描述 :

由于长期缺乏运动,小黑发现自己的身材臃肿了许多,于是他想健身,更准确地说是减肥。
小黑买来一块圆形的毯子,把它们分成三等分,分别标上A,B,C,称之为“跳舞毯”,他的运动方式是每次都从A开始跳,每次都可以任意跳到其他块,但最后必须跳回A,且不能原地跳.为达到减肥效果,小黑每天都会坚持跳n次,有天他突然想知道当他跳n次时共几种跳法,结果想了好几天没想出来-_-
现在就请你帮帮他,算出总共有多少跳法。

输入:

测试输入包含若干测试用例。每个测试用例占一行,表示n的值(1<=n<=1000)。
当n为0时输入结束。

输出:

测试输入包含若干测试用例。每个测试用例占一行,表示n的值(1<=n<=1000)。
当n为0时输入结束。

样例输入:

2
3
4
0

样例输出:

2
2
6

点击打开链接

dp[i]=dp[i-1]+2*dp[i-2]

#include"stdio.h"
int main()
{
	__int64 dp[1005];
	int i;
	int n;
	dp[1]=0;
	dp[2]=2;
	for(i=3;i<=1000;i++)
	{
		dp[i]=dp[i-1]+2*dp[i-2];
		dp[i]%=10000;
	}
	while(scanf("%d",&n)!=EOF&&n!=0)
		printf("%I64d\n",dp[n]);
	return 0;
}

解题转自:http://blog.csdn.net/yangyafeiac/article/details/7828367


  1. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1

  2. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  3. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  4. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  5. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。