首页 > 试题广场 >

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

阿克

a[i]=((a[i-1]+a[i-2])%1000000007+a[i-3])%1000000007
的解释：
取模运算有这样一个性质：(a+b)%c = ((a%c)+(b%c))%c
所以(a[i-1]+a[i-2])%1000000007就相当于(a[i-1]%X+a[i-2]%X)%X   用X代替1000000007
这样就使得a[i-1]、a[i-2]、a[i-1]+a[i-2]都没有溢出，之后再与a[i-3]相加之后取模，使得全部结果没有溢出。

编辑于 2016-03-15 22:01:08 回复(3)

Leon_z

//只需要额外申请三个空间存放a,b,c，减小了空间复杂度
class GoUpstairs {
public:
    int countWays(int n) {
        // write code here
        int a=1;
        int b=2;
        int c=4;
        if(n<1) return 0;
        if(n==1) return a;
        if(n==2) return b;
        if(n==3) return c;
        for(int i=4;i<=n;i++){
            int temp=((a+b)%1000000007+c)%1000000007;
            a=b;b=c;c=temp;
        }
        return c;
    }
};

发表于 2018-03-16 19:48:42 回复(0)

MichaelTim

//对于上k级台阶,当k>3时，由于每次可以上1,2,3级，则最后一次应该是上1,2,3中的一个
//case1，最后一次上1级，也即前面上了k-1级，k-1级的可能情况为：A[k-1]次
//同理 case2,A[k-1], case3 A[k-3]
//从而有： A[k] = A[k-3] + A[k-2] + A[k-1] 
class GoUpstairs {
public:
	int countWays(int n) {
		long long resMid;
		long long frontWay[3] = { 1, 2, 4 };
		if (n < 4) return frontWay[n - 1];
		for (int i = 3; i < n; i++){
			long long temp = frontWay[0] + frontWay[1] + frontWay[2];
			frontWay[0] = frontWay[1];
			frontWay[1] = frontWay[2];
			frontWay[2] = temp;
			if (frontWay[2] > 1000000007){
				frontWay[2] = frontWay[2] % 1000000007;
			}
		}
		int res = frontWay[2] % 1000000007;
		return res;
	}
};

发表于 2016-09-17 19:15:43 回复(1)

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)

C/C++

kakaan

斐波那契数列高级版，用空间换时间

    int countWays(int n) {
        int a[100000];
        a[0] = 1;
        a[1] = 2;
        a[2] = 4;
        for(int i=3;i<n;i++)
            a[i] = ((a[i-1]+a[i-2])% 1000000007+a[i-3]) % 1000000007;
        return a[n-1];
    }

发表于 2016-09-01 17:29:22 回复(1)

neo007

class GoUpstairs {
public:
    int countWays(int n) {
        if(n==0){
        }
        if(n==1){
            return 1;
        }
        int a = 1;
        int b = 1;
        int c = 2;
        for(int i=3;i<=n;i++){
            int temp = ((a+b)%1000000007+c)%1000000007;
            a = b;
            b = c;
            c = temp; 
        }
        return c;
    }
};

编辑于 2016-09-13 10:11:48 回复(0)

xiaoyuyu

import java.util.*;

public class GoUpstairs {
    
    public int countWays(int n) {
        // write code here
        long[] pre = {1, 2, 4};
        if(n<=0) return 0;
        else if(n<=3) return (int)pre[n-1];
        else{
            for(int i=4; i<=n; i++){
                long tmp = ((pre[0] + pre[1])%1000000007 +pre[2])%1000000007;
                pre[0] = pre[1];
                pre[1] = pre[2];
                pre[2] = tmp;
            }
        }
        return (int)pre[2];
    }
}

发表于 2016-08-26 10:42:52 回复(0)

棉花汤

class GoUpstairs {
public:
    long long countWays(int n) {
        long long arr[100001];
        arr[1] = 1;
        arr[2] = 2;
        arr[3] = 4;
        for(int i = 4;i<=100001;++i)
			arr[i] = (arr[i-1]+arr[i-2]+arr[i-3])%1000000007;
		return arr[n];
    }
};

发表于 2016-08-22 17:18:39 回复(0)

忆水寒

class GoUpstairs {
public:
    int countWays(int n) {
        // write code here
        int f1=1;
        int f2=2;
        int f3=4;
        int result=0;
        if(n<=0) return 0;
        if(n==1) return 1;
        if(n==2) return 2;
        if(n==3) return 4;
        for(int i=4;i<=n;i++)
        {
            result=((f3+f2)%1000000007+f1)%1000000007;
            f1=f2;
            f2=f3;
            f3=result;
        }
       return result;
    }
};

发表于 2016-07-22 10:20:34 回复(0)

暁仨畀

首先题目描述错误：不是大于等于n而是直到等于n；

其次题目给的mod1000000007是个陷阱，因为每次递归返回时为三个数相加直接取余依旧会导致溢出，合理做法是将(a+b+c)%1000000007改为(((a+b）%1000000007)+c)%100000007

class GoUpstairs {
public:
    int countWays(int n) {
        // write code here
        int *N=(int *)malloc(sizeof(int)*n);
        memset(N,0, sizeof(N));
		N[0]=1;N[1]=2;N[2]=4;
		for(int i=3;i<n;i++){
		    N[i]=(((N[i-3]+N[i-2])%1000000007)+N[i-1])%1000000007;
		}
		return N[n-1];
        
    }
};

发表于 2020-12-19 22:00:02 回复(0)

南少201911241210480

class GoUpstairs {
public:
    int countWays(int n) {
        // write code here
        int a[]={0,1,2,4};
        int f;
        if(n<4)
            return a[n];
        for(int i=4;i<=n;i++)
        {
            f=((a[1]+a[2])%1000000007+a[3])%1000000007;
            a[1]=a[2];
            a[2]=a[3];
            a[3]=f;
        }
        return a[3];
    }
};

数学规律f(i)=f(i-1)+f(i-2)+f(i-3)。f(i-1)+f(i-2)+f(i-3)每两个相加都有可能大于100000007，所以在每次相加后取模。

发表于 2020-03-05 12:58:12 回复(0)

zbbsyx

class GoUpstairs {
public:
    int countWays(int n) {
        // write code here
        int dp[4], res;
        dp[1] = 1, dp[2] = 2, dp[3] = 4;
        if(n <= 3) res = dp[n];
        for (int j = 4; j <= n ; ++j) {
            res = ((dp[1] + dp[2]) % 1000000007 + dp[3]) % 1000000007;
            dp[1] = dp[2];
            dp[2] = dp[3];
            dp[3] = res;
        }
        return res;
    }
};

发表于 2019-06-11 15:39:44 回复(0)

木然猫猫

# -*- coding:utf-8 -*-
class GoUpstairs:
    def countWays(self, n):
        dp = [0] * (n+1)
        dp[1] = 1
        dp[2] = 2
        dp[3] = 4
        for i in range(4, n+1):
            dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % 1000000007
        return dp[n]

运行时间：754ms

占用内存：9132k

发表于 2018-12-19 12:21:02 回复(0)

小猪佩7

//不另外开辟数组空间，定义几个变量依次移动
public int countWays(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 4;
        int mod = 1000000007;
        int first = 1;
        int second = 2;
        int third = 4;
        int result = 0;
        for (int i = 4; i <= n; i++) {
            result = (first + second) % mod + third % mod;
            first = second % mod;//依次往后移动一位数
            second = third % mod;
            third = result;
        }
        return result % mod;
    }

发表于 2018-03-11 10:42:05 回复(0)

BrainerGao

//Fibonacci sequence f(n) = f(n-1)+f(n-2)+f(n-3); And f(1)=1,f(2)=2,f(3)=4
import java.util.*; public class GoUpstairs {
    public int countWays(int n) {
        int[] arr = {1, 2, 4};
        if(n <= 0){
            return 0;
        } else if(n <= 3){
            return arr[n-1];
        } else {
            for(int i = 4; i <= n; i++){
                int tmp = ((arr[0] + arr[1]) % 1000000007 + arr[2]) % 1000000007;
                arr[0] = arr[1];
                arr[1] = arr[2];
                arr[2] = tmp;
            }
        }
        return arr[2];
    }
}

发表于 2017-05-20 23:08:07 回复(0)

牛客543826号

/*
    模运算有一个特点就是 (a + b) % c  相当于
    ((a %c + b%c) % c)
   另外注意到每次当前状态 i 只与前三个状态有关，因此可以只申请3个空间的数组，每次状态i模3
   就可以了。
    */
    public int countWays(int n) {
        // write code here
        if (n <= 0) {
            return 0;
        }
		
        long[] res = new long[3];
        res[0] = 1;
        res[1] = 2;
        res[2] = 4;
        int mod = 1000000007;
        for (int i = 3; i < n; ++i) {
            res[i % 3] = (res[(i - 1) % 3] + res[(i - 2) % 3] + res[(i - 3) % 3]) % mod;
        }
        
        return (int)res[(n - 1) % 3];
    }

发表于 2017-02-28 21:10:37 回复(0)

HelloWorldn

package 上楼梯;

public class GoUpstairs {

private static final int MOD = 1000000007;
public int countWays(int n) {
    // write code here
    if (n == 1)
        return 1;
    if (n == 2)
        return 2;
    if (n == 3)
        return 4;
    // 利用三元一次方程组手算的base
    int[][] base = { { 1, 1, 0 }, { 1, 0, 1 }, { 1, 0, 0 } };
    int[][] res = new int[base.length][base[0].length];
    for (int i = 0; i < res.length && i < res[0].length; i++) {
        res[i][i] = 1;
    }
    res = matrixPower(base, n - 3, res);
    //return (4 * res[0][0] + 2 * res[1][0] + res[2][0]) % MOD;
    int[][] a = {{4,2,1}};
    res = multiMatrix(a, res);
    return res[0][0];
}

private int[][] matrixPower(int[][] base, int n, int[][] res) {
    if (0 == n) {
        return res;
    } else {
        if ((1 & n) == 0) { // 如果n是偶数
            return matrixPower(multiMatrix(base, base), n / 2, res);
        } else {
            return matrixPower(base, n - 1, multiMatrix(res, base));
        }
    }
}

private int[][] multiMatrix(int[][] m1, int[][] m2) {
    int[][] res = new int[m1.length][m2[0].length];
    int m1_row = m1.length;
    int m1_col = m1[0].length;
    int m2_col = m2[0].length;
    for (int i = 0; i < m1_row; i++) {
        for (int j = 0; j < m2_col; j++) {
            for (int k = 0; k < m1_col; k++) {
                long tmp = ((long)(m1[i][k] % MOD) * (long)(m2[k][j]%MOD));
                long tmp2 = (tmp % (long)MOD);
                int tmp3 = (int)tmp2;
                res[i][j] = (tmp3 + res[i][j]) % MOD;
            }
        }
    }
    return res;
}

public static void main(String[] args) {
    GoUpstairs go = new GoUpstairs();
    System.out.println(go.countWays(36196));
}

}

编辑于 2016-11-29 13:57:35 回复(3)

uniwjj

import java.util.*;

public class GoUpstairs {
    public int countWays(int n) {
        if (n <= 0) return 0;
        if (n <= 3) return 1 << (n-1);
            
        int[] f = {1, 2, 4};
        int result = 0;
        for (int i = 4; i <= n; i++) {
        	result = (((f[0] + f[1]) % 1000000007) + f[2]) % 1000000007;
            f[0] = f[1];
            f[1] = f[2];
            f[2] = result;
        }
        return result;
    }
}

发表于 2016-08-09 21:54:02 回复(0)

Aurora1

    public int countWays(int n) {
		int a[] = { 1, 1, 2 };
		if (n < 3) {
			return a[n];
		}
		int i = 3;
		for (; i <= n; i++) {
			int x = 0;
			for (int j = 0; j < 3; j++) {
				x += a[(i + j) % 3];
				x %= 1000000007;
			}
			a[i % 3] = x;
		}

		return a[(i - 1) % 3];
	}

发表于 2016-04-11 16:26:19 回复(0)

datong

class GoUpstairs {
public:
    int countWays(int n) {
        if(n <= 0) return n;
        if(n == 3) return 4;
        long p = 1, q = 2, k =4;
        int i = 3;
        long fn = k;
        while(n != i){
            fn = (p + q + k)%1000000007;
            p = q%1000000007;
            q = k%1000000007;
            k = fn;
            ++ i;
        }
        return fn;
    }
};

发表于 2015-09-14 14:01:43 回复(0)