老板发奖金

[编程题]老板发奖金

热度指数：3376 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

老板一共需要给某个员工发奖金n元，可以选择一次发1元，也可以选择一次发2元，也可以选择一次发3元。请问老板给这位员工发放完n元奖金共有多少种不同的方法？

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

示例1

输入

输出

说明

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

示例2

输入

输出

说明

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

备注:

输入参数为一个整数数字，输出为一个整数数字

算法知识视频讲解

Java

牛客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)