首页 > 试题广场 >

加到n

[编程题]加到n
  • 热度指数：25653 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

给定一个正整数int n，从0开始加到n，每次可增加1、2或3，直到其大于等于n，请返回一个数，代表加到n的方案的个数。保证n小于等于100000，并为了防止溢出，请将结果Mod 1000000007。

测试样例1： 
1
返回：1
测试样例2： 
3
返回：4
测试样例3： 
4
返回：7

算法知识视频讲解
添加回答
推荐
WNDKSJDM头像 WNDKSJDM
class GoUpstairs {
public:
    int countWays(int n) {
        int a[100000];
       for(int i=0;i<=100000;i++)
          a[i]=0;
          a[1]=1;
          a[2]=2;
          a[3]=4;
      for(int i=4;i<=n;i++)
          a[i]=((a[i-1]+a[i-2])%1000000007+a[i-3])%1000000007;
      return a[n];
    }
}; 
//递归法
	/**
	 * 思路：自上而下的方式。
	 * 最后一步可能是从第n-1阶往上走1阶、从第n-2阶往上走2阶或从第n-3阶往上走3阶。
	 * 因此，抵达最后一阶的走法，抵达这最后三阶的方式的综合。
编辑于 2016-03-15 22:09:23 回复(7)
提交观点

问题信息

动态规划 递归
难度：
0条回答 25901浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号