首页 > 试题广场 >

老板发奖金

[编程题]老板发奖金
  • 热度指数：3376 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
老板一共需要给某个员工发奖金n元，可以选择一次发1元，也可以选择一次发2元，也可以选择一次发3元。请问老板给这位员工发放完n元奖金共有多少种不同的方法？

数据范围：1 <= n <= 10
示例1

输入

2

输出

2

说明

一共有2元奖金，有两种发放方法；第一中：分别每次发放1元，两次发放完，第二种一次全部发放完
示例2

输入

3

输出

4

说明

一共有3元奖金，有4种发放方法；第一种：分别每次发放1元，3次发放完，第二种先第一次发2元，第二次发1元； 第三种第一次发1元，第二次发2元； 第四种方法一次全部发放完

备注:
输入参数为一个整数数字，输出为一个整数数字
算法知识视频讲解
添加回答
秒速一千米头像 秒速一千米
分析：可以这样想，发5元怎么发？
1：先发1块的情况下，剩下4块是不是就和发4块的方法一样了？
2：先发2块的情况下，剩下3块是不是就和发3块的方法一样了？
3：先发3块的情况下，剩下2块是不是就和发2块的方法一样了？
4：先发4块的情况下，剩下1块是不是就和发1块的方法一样了？
5：5块一次性发完，唯一方法
这很递归嘛~
即符合  f(n) = f(n-1) + f(n-2) + ... + f(1) + 1

为便于理解，本人画了张图。
代码和运行结果如下 
public class GiveMoney {
    public static void main(String[] args) {
        Scanner scanner = new Scanner (System.in);
        System.out.print ("输入要发的奖金:");
        int number = scanner.nextInt ();
        System.out.println ("您有" + f (number) + "种方法发完" + number + "元奖金!!");
    }

    /**
     * 获取 发奖金可用的总方法 的方法
     *
     * @param number 要发的钱数
     * @return 总方法数
     */
    public static int f(Integer number) {
        // 设置递归结束条件
        if (number == 1) {
            return 1;
        }
        // 实现 f(n) = f(n-1) + f(n-2) + ... + f(1) + 1
        int count = 0;
        for (int i = number - 1; i >= 1; i--) {
            count = f (i) + count;
        }
        return count + 1;
    }
}

发表于 2022-01-22 22:33:34 回复(6)
我要逆天当学霸头像 我要逆天当学霸
import java.util.*;
public class Solution {
    /**
     * 
     * @param num_money int整型 奖金的总数,单位为元
     * @return int整型
     */
    public void main(String [] args){
        Scanner sc = new Scanner(System.in);
        int num_money = sc.nextInt();
        System.out.println(CalulateMethodCount(num_money));
        sc.close();
    }
    public int CalulateMethodCount (int num_money) {
        // write code here
        if (num_money == 1) return 1;
        if (num_money == 2) return 2;
        if (num_money == 3) return 4;
        int[] dp = new int[num_money + 1];
        dp[0] = 0; 
        dp[1] = 1; 
        dp[2] = 2; 
        dp[3] = 4;
        for (int i = 4; i <= num_money; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        return dp[num_money];
    }
}

发表于 2022-01-20 21:32:27 回复(5)
橘子橘子999头像 橘子橘子999
这不就是 青蛙跳吗
发表于 2022-02-23 22:26:19 回复(0)
TPH-BETTER.头像 TPH-BETTER.
以5元为例
先发1元，剩下4元就和一共发4元的方法一样了。
先发2元，剩下3元就和一共发3元的方法一样了。
先发3元，剩下2元就和一共发2元的方法一样了。

以6元为例
先发1元，剩下5元就和一共发5元的方法一样了。
先发2元，剩下4元就和一共发4元的方法一样了。
先发3元，剩下3元就和一共发3元的方法一样了。

也就是f(n)=f(n-1)+f(n-2)+f(n-3)
f(1)=1
f(2)=2
f(3)=4


import java.util.*;
public class Solution {
    /**
     *
     * @param num_money int整型 奖金的总数,单位为元
     * @return int整型
     */
    public static int CalulateMethodCount (int num_money) {
        //递归结束条件
        if(num_money==1){
            return 1;
        }else if(num_money==2){
            return 2;
        }else if(num_money==3){
            return 4;
        }
        int count=0;
        for(int i=num_money-1;i>=num_money-3;i--){
            count+=CalulateMethodCount(i);
        }
        return count;

    }
}

编辑于 2022-05-09 12:51:28 回复(2)
牛客95393832号头像 牛客95393832号
 int a = 0;
if( num_money >= 3){
        for(int i = num_money - 1; i > 1; i--){
            a = a+i;
        }
        return a+2;
    }else{
        return num_money;
}
解析：
输入1，输出：1=1
输入2，输出：2=1+1
输入3，输出：4=2+1+1
输入4，输出：7=3+2+1+1
所以找到规律了，这个规律从3开始，你们着重看一下我给i赋的初始值就明白了。
自测成功后，切记要保存代码，我忘记保存代码了。。。。。。。。。

发表于 2022-01-19 14:43:11 回复(6)
sssgggjjj头像 sssgggjjj
import java.util.*;


public class Solution {
    /**
     * 
     * @param num_money int整型 奖金的总数,单位为元
     * @return int整型
     */
    public int CalulateMethodCount (int num_money) {
        // write code here
        if(num_money == 1){
            return 1;
        }
        if(num_money == 2){
            return 2;
        }
        if(num_money == 3){
            return 4;
        }
        return CalulateMethodCount(num_money-1) + CalulateMethodCount(num_money-2) + CalulateMethodCount(num_money-3);
    }
}
好久没写算法了,看到这题,一瞬间想到了上台阶的问题,一步走一个台阶还是两个台阶,本题的思想就可以看成上台阶的问题，将题理解成n层台阶一步能走1-3个台阶。走到n层台阶有多少种走法。

因为想一步到达n层台阶,只能在n-1,n-2,n-3其中一层台阶,当在n-1层时只需要一次性上1个台阶,n-2层时只需要上2个台阶,n-3层只需要一次性上3个台阶。通过这里我们就会发现想要求出走到n层台阶有多少种走法, 就要求出走到n-1层,n-2层,n-3层各有多少种走法,加和之后就是走到n层一共有多少走法。
用一个简单的数学公式表示就是:F(n) = F(n-1)+F(n-2)+F(n-3)。 

第一次评论算法题,可能写的不是很透彻,算法想的有些复杂,欢迎大佬留言指正。
发表于 2023-04-21 12:00:37 回复(0)
牛客877676053号头像 牛客877676053号
分享一下js的 
function CalulateMethodCount( num_money ) {
    // write code her
        if (num_money == 1) return 1;
        if (num_money == 2) return 2;
        if (num_money == 3) return 4;
        let dp = new Array(num_money + 1).fill(0);
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for (let i = 4; i <= num_money; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        return dp[num_money];
}
module.exports = {
    CalulateMethodCount : CalulateMethodCount
};

发表于 2022-08-25 18:16:08 回复(0)
牛客99025299号头像 牛客99025299号 

int CalulateMethodCount(int num_money ) {
    // write code here
    // 设置递归结束条件
     if(num_money==1){
        return 1;
    }else if(num_money==2){
        return 2;
    }else if(num_money==3){
        return 4;
    }
    int count=0;
    for(int i=num_money-1;i>=num_money-3;i--){
        count+=CalulateMethodCount(i);
    }
    return count;
}

发表于 2022-07-13 16:22:06 回复(0)
牛客193692213号头像 牛客193692213号 
public class other_3 {

    /*思路：
    以5元为例
    先发1元，剩下4元就和一共发4元的方法一样了。
    先发2元，剩下3元就和一共发3元的方法一样了。
    先发3元，剩下2元就和一共发2元的方法一样了。
    也即：f(n)=f(n-1)+f(n-2)+f(n-3)
    */
    public int CalulateMethodCount(int num_money) {
        // write code here
        return  dfs(num_money);

    }

    int dfs(int money) {
        if (money==1)
            return 1;
        if (money==2)
            return 2;
        if (money==3)
            return 4;

        return dfs(money-1)+dfs(money-2)+dfs(money-3);

    }
}

发表于 2023-10-11 10:06:47 回复(0)
tlwaj头像 tlwaj
典型的动态规划问题啦~~~ 
/**
 * 
 * @param num_money int整型 奖金的总数,单位为元
 * @return int整型
 */
function CalulateMethodCount( num_money ) {
    // write code here
    let dp = new Array(num_money).fill(0);
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for (let i = 4; i <= num_money; i++) {
        dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
    }
    return dp[num_money];
}
module.exports = {
    CalulateMethodCount : CalulateMethodCount
};


发表于 2023-03-12 23:30:38 回复(0)
没用的贝极星捏头像 没用的贝极星捏 
import java.util.*;
//可以参考下爬楼梯，可以走1步2步或者3步，走到目标阶层

public class Solution {
    /**
     * 
     * @param num_money int整型 奖金的总数,单位为元
     * @return int整型
     */
    public int CalulateMethodCount (int num_money) {
        // write code here
        int[] arr = new int[]{1,2,3};
        int[] dp = new int[num_money + 1];
        dp[0] = 1;
        for(int i = 1;i <= num_money;i++){
            for(int j = 0;j < 3;j++){
                if(arr[j] <= i)
                dp[i] += dp[i - arr[j]];
            }
        }
        return dp[num_money];
    }
}
发表于 2022-09-27 01:09:53 回复(0)
Java
牛客118090258号头像 牛客118090258号

//回溯法
public class Solution {

static int count = 0;
public int CalulateMethodCount (int num_money) {
    // write code here
    int[] arr = {1,2,3};
    backTracking(arr,num_money,0);
    return count;
}

public void backTracking(int[] arr,int n,int sum){
    if(sum == n){
        count++;
        return;
    }
    for (int i = 0; i < arr.length; i++) {
        if(sum+arr[i] > n){
            break;
        }
        sum += arr[i];
        backTracking(arr,n,sum);
        sum -= arr[i];
    }
}

}

发表于 2022-09-16 16:39:29 回复(0)
什么大肥猪头像 什么大肥猪 
package main
 
/**
 *
 * @param num_money int整型 奖金的总数,单位为元
 * @return int整型
*/
func CalulateMethodCount(num_money int) int {
    // write code here
    if num_money == 1 {
        return 1
    }
    if num_money == 2 {
        return 2
    }
    if num_money == 3 {
        return 4
    }
    return CalulateMethodCount(num_money-1) + CalulateMethodCount(num_money-2)+ CalulateMethodCount(num_money-3)
}斐波那契数列的简单应用
发表于 2022-08-25 17:35:17 回复(0)
九里258头像 九里258 


class Solution:
    def CalulateMethodCount(self , num_money ):
        # write code here
        if num_money<=0:
            return 0
        if num_money==1:
            return 1
        if num_money==2:
            return 2
        if num_money==3:
            return 4
        a=4
        b=2
        c=1
        sum1=0
        for i in range(4,num_money+1):
            sum1 = a+ b + c
            c = b
            b = a
            a=sum1
        return sum1
编辑于 2022-08-23 22:39:55 回复(0)
牛客42659513号头像 牛客42659513号
dp 
package main
 
/**
 *
 * @param num_money int整型 奖金的总数,单位为元
 * @return int整型
*/
func CalulateMethodCount( num_money int ) int {
    // write code here
    slove := make([]int, num_money+1)
    slove[0] = 1
    slove[1] = 1
    slove[2] = 2
    slove[3] = 4
    if num_money <= 3 {
        return slove[num_money]
    }
    for i := 4; i <= num_money; i++ {
        slove[i] = slove[i-1] + slove[i-2] + slove[i-3]
    }
    return slove[num_money]
}


编辑于 2022-06-02 19:41:26 回复(0)
offer捏头像 offer捏 


n = int(input()) def digui(n): out = 0    if n == 1:
        out = 1    elif n == 2:
        out = 2    elif n == 3:
        out = 4    else:
        out = digui(n-1) + digui(n-2) + digui(n-3)  return out  print(digui(n))
编辑于 2022-05-18 10:51:13 回复(0)
4fbd81e头像 4fbd81e 
#
# 
# @param num_money int整型 奖金的总数,单位为元
# @return int整型
#
from functools import *

@lru_cache(maxsize=None)
def func(n):
        # write code here
        if n==1:
            return 1
        elif n==2:
            return 2
        elif n==3:
            return 4
        else:
            return func(n-1)+func(n-2)+func(n-3)


class Solution:
    def CalulateMethodCount(self , n):
        return func(n)
    

发表于 2022-05-02 13:51:57 回复(0)
lbw_993头像 lbw_993
直接递归把所有情况跑一遍，钱刚好发完结果就加1 
import java.util.*;


public class Solution {
    /**
     * 
     * @param num_money int整型 奖金的总数,单位为元
     * @return int整型
     */
    public int CalulateMethodCount (int num_money) {
        // write code here
        fajangjin(0,num_money);
        return result;
    }
    
    private Integer result = 0;
    private void fajangjin(int c, int n) {
        if(c == n) {
            result++;
            return ;
        }

        for(int i=1;i<=3;i++){
            if(c+i<=n){
                fajangjin(c+i, n);
            }
        }
    }
}


发表于 2022-03-30 19:18:45 回复(0)
牛客624203423号头像 牛客624203423号 
package main

/**
 * 
 * @param num_money int整型 奖金的总数,单位为元
 * @return int整型
*/
func CalulateMethodCount( num int ) int {
   	if num == 0 {
		return 0
	} else if num == 1 || num == 2 {
		return num
	} else if num == 3 {
		return 4
	}
	return CalulateMethodCount(num-1) + CalulateMethodCount(num-2) + CalulateMethodCount(num-3)

}

发表于 2022-03-18 16:55:35 回复(0)
OFFER/OFFER头像 OFFER/OFFER
简单动规 
class Solution 
{
public:
    /**
     * 
     * @param num_money int整型 奖金的总数,单位为元
     * @return int整型
     */
    int CalulateMethodCount(int num_money) 
    {
        // write code here
        vector<int> dp(num_money + 1, 0);
        dp[0] = 1;
        for(int i = 1;i <= num_money;i++)
        {
            dp[i] += dp[i-1];
            if(i > 1)
                dp[i] += dp[i-2];
            if(i > 2)
                dp[i] += dp[i-3];
        }
        return dp[num_money];
    }
};


发表于 2022-03-17 18:34:12 回复(0)
提交观点

问题信息

上传者：小小
难度：
21条回答 2982浏览

热门推荐

通过挑战的用户

相关试题

老板发奖金

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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