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];
    }
};