[数据结构与算法]每日一小题

机器人一次可以走1m，2m或3m。编写一个动态规划算法求机器人走n米有多少种走法
简单的一种递推思想
当n 1时，只有一种解法
当n 2时，有两种。
当n == 3时，有四种。
1 1 1，2 1，1 2 ，3.
当n4时，有七种。
1 1 1 1，1 3 ，3 1，2 2，2 1 1，1 1 2，1 2 1.
当n5时，有十三种。
1 1 1 1 1，1 1 1 1 2，1 1 2 1，1 2 1 1，2 1 1 1，
1 2 2，2 1 2，2 2 1，1 1 3，
1 3 1 ，3 1 1， 3 2 ，2 3 .
得到当n>3时，S(n)=S(n-1)+S(n-2)+S(n-3);

#include<stdio.h>
int path(int n);
int main()
{
	int n;
	scanf("%d",&n);
	n=path(n);
	printf("%d",n);
	return 0;
} 
int path(int n)
{
	if(n==1) return 1;
	else if(n==2) return 2;
	else if(n==3) return 4;
	else if(n>3) return path(n-1)+path(n-2)+path(n-3);
}

还有一博主的方法也不错，总体来说递归还是占用空间比较多的。

/*
 * 题目：
 * 一个机器人每步可以走 1 米、2 米或 3 米。
 * 编写一个动态规划算法，计算机器人走n 米，有多少种走法（考虑步骤的次序）。
 *
 *
 * 算法思路：
 * 设总路程为n米，共有s(n)种走法
 *
 * 假设初值s(0) = 1
 * 易知s(1) = 1  s(2) = 2
 * 可以求出递推式：s(n) = s(n - 1) + s(n - 2) + s(n - 3) 
 *
 * 递归求s(n)的方法：return s(n - 1) + s(n - 2) + s(n - 3);
 * 用动态规划求解：
 * 建立一个长度为3的数组，将每次运算的结果存进数组中，最后数组的和即为所求
 * 这样可以避免每次计算s(i)都要从s(0) + s(1) + s(2) 算起
 *
 * 时间复杂度：Θ(n) 
 * 空间复杂度：Θ(1)
 *
 */
 
#include <iostream>
using namespace std;
 
int robotWalk(int n)
{
	int a[3] = {1, 1, 2};
 
	if(n <= 0)
	{
		return 0;
	}
	else if(n == 1)
	{
		return a[1];
	}
	else if(n == 2)
	{
		return a[2];
	}
	else
	{
		int count = 0;
		int temp = 0;
		for(int i = 2; i < n; i++)
		{
			temp = a[2] + a[1] + a[0];
			a[count] = temp;
			count = (count + 1) % 3;
		}
 
		return temp;
	}
}
 
int main()
{
	int n;
	char ch = 'y';== 'Y')
	{
	while(ch == 'y' || ch 
		cout<<"请输入机器人的总路程:";
		cin>>n;
		if(n < 0)
		{
			cout<<"输入错误，总路程必须大于等于0"<<endl;
		}
		cout<<"共有"<<robotWalk(n)<<"种走法"<<endl;
 
		cout<<endl<<"是否继续?y/n:";
		cin>>ch;
	}
 
	return 0;
}