我要招人

去企业版

首页 > 试题广场 >

加到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

测试样例2：

返回：4

测试样例3：

返回：7

算法知识视频讲解

推荐

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)

Java

天山剑客

public class GoUpstairs {
    public int countWays(int n) {
        // write code here
    	if (n == 1) {
    		return 1;
    	}
    	
    	if (n == 2) {
    		return 2;
    	}
    	
    	if (n == 3) {
    		return 4;
    	}
    	
        // 数组下标n-1表示n阶台阶的走法
    	int count = 0;
    	int n1 = 1;
    	int n2 = 2;
    	int n3 = 4;
    	if (n > 3) {
    		for (int i = 4; i <= n; i++) {
    			count = ((n1 + n2)%1000000007 + n3)%1000000007;
    			n1 = n2;
    			n2 = n3;
    			n3 = count;
    		}
    	}
    	
    	return count;
    }
}

发表于 2019-12-12 12:17:43 回复(0)

Java

安徒生的谎言

import java.util.*;

public class GoUpstairs {
     public int countWays(int n) {
        // write code here
        int[] dp=new int[n+1];
        dp[1]=1;
        dp[2]=2;
        dp[3]=4;
        for(int i=4;i<=n;i++){
            dp[i]=((dp[i-1]+dp[i-2])%1000000007+dp[i-3])%1000000007;
        }
         return dp[n];
    }
}

发表于 2018-01-27 15:09:58 回复(0)

Java

面什么过什么

import java.util.*;

public class GoUpstairs {
    public int countWays(int n) {
        // write code here
        if (n < 0) {
            return 0;
        } else if (n == 0) {
            return 1;
        }
        int f0 = 0, f1 = 0, f2 = 1, f3 = 0;
        for (int i = 1; i <= n; i++) {
            f3 = ((f1 + f2) % 1000000007 + f0) % 1000000007;
            f0 = f1;
            f1 = f2;
            f2 = f3;
        }
        return f3;
    }
}

发表于 2017-07-25 19:40:10 回复(0)

Java

Holiday_12138

import java.util.*;

public class GoUpstairs {
    public int countWays(int n) {
        int t1=0,t2=0,t3=1;
        int cur=0;
        while(n-->0){
            cur=((t1+t2)%1000000007+t3)%1000000007;
            t1=t2%1000000007;
            t2=t3%1000000007;
            t3=cur%1000000007;
        }
        return cur;
    }
}

发表于 2017-04-18 13:35:20 回复(0)

Java

agjsytt

参考某神的指导: "n阶对应的上法=(n-1)阶,(n-2)阶,(n-3)阶的走法总数."

依据排列组合中"分类加法计算原理".

http://baike.baidu.com/link?url=jRo8M2fJEqjw6neQsLSuCLSJ2leuW9ts08GkjuDTcIM_GpU6dSNN5AvYtlduwXRvVdtRpHaztru7upqaUpWJVFi-JVyB2beg_P27BbaTINtFheCsWxKGNuXa9LXrUz-dlnat6VUp-qbV-GLiiZmucaZrcVkY8hyuLMDi56oHISO

按照最后一步跨越的阶数,分为1阶,2阶,3阶.三类之和即为总的走法数.

设:

f(n): n阶对应的走法数.

则: f(n) = f(n-1)+f(n-2)+f(n-3);

double[] r = new double[n];
        if (n >= 1) {
            r[0] = 1;
        }
        if (n >= 2) {
            r[1] = 2;
        }
        if (n >= 3) {
            r[2] = 4;
        }
        for (int i = 3; i < n; i++) {
            r[i] = (r[i - 1] + r[i - 2] + r[i - 3]) % 1000000007;
        }
        return (int) r[n - 1] % 1000000007;

编辑于 2016-11-15 20:53:26 回复(0)

Java

牛客334705号

状态：d[i]

状态转移方程：d[i] = d[i-3] + d[i-2] + d[i-1]

故

public static int countWays(int n) {
		int[] d = new int[n];
		d[0] = 1;
		if(n<3)
			return n;
		else if(n==3)
			return 4;
		else{
			d[0] = 1;
			d[1] = 2;
			d[2] = 4;
				
		}
		
		for(int i=3;i<d.length;i++){
			for(int j=0;j<3;j++){
				d[i] = (d[i-3]+(d[i-2]+d[i-1])%1000000007)%1000000007;
			}
		}
		return d[n-1];
	}

发表于 2016-08-04 01:44:19 回复(0)

Java

鈞嘢嘢

public int countWays(int n) {
        // write code here
        if (n < 1)
            return 0;
        if (n == 1 || n == 2)
            return n;
        if (n == 3)
            return 4;
        return ((countWays(n-1) + countWays(n-2)) % 1000000007 + countWays(n-3)) % 1000000007;
    }

为什么用递归调用不行？

提示运行错误:请检查是否存在数组越界非法访问，野指针乱访问，空指针乱访问等情况

发表于 2016-07-06 01:07:47 回复(2)