QAX笔试编程题1——老板发奖金

1. 老板发奖金

• 题目描述：老板一共需要给某个员工发奖金n元，可以选择一次发1元，也可以选择一次发2元…也可以选择一次发n元（必须以元为正数单位发放）。请问老板给这位员工发放完n元奖金共有多少种方法？

• 分析：

  乍一看就是青蛙跳台阶问题的变态，之前有做过青蛙跳台阶的斐波那契解法，也做过变态解法。但是在考试时用这个解法并不能通过测试平台。难道是因为我没有写头文件这些内容，但系统明明是有函数定义接口的，于是直接写了函数。。。

• 代码：

  如果是变态跳台阶问题，代码就是：

#include<iostream>
using namespace std;

int Solution(int n)
{
	if(n<=0)
		return 0;
	if(n ==1)
		return 1;
	if(n>=2)
		return 2*Solution(n-1);
}

int main()
{
	int n;
	cin>>n;
	int r = Solution(n);
	cout<<r;
	return 0;
}
           

但我试过没用，而且牛客上大家也是这么说的，还有人说用三步问题解AC了，但这明显与题意是不符的。

三步问题是跳1,2层台阶问题的一个变形，用动态规划相对比较好理解些，leecode上的三步问题代码如下：

注意要用

long int

来定义动态规划数组类型！

class Solution {
public:
    int waysToStep(int n) 
    {
        int MOD = 1000000007;

        if(n <= 2)
            return n;

        vector<long int> dp(n+1);
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for(int i=4;i<=n;i++)
        {
            dp[i] = (dp[i-1] + dp[i-2] + dp[i-3])%MOD;
        }
        return dp[n];
    }
};