老板发奖金

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

1. 使用递归求解

递归两大核心： 1. 边界条件 2. 递归

1：先发1块的情况下，剩下4块是不是就和发4块的方法一样了？

2：先发2块的情况下，剩下3块是不是就和发3块的方法一样了？

3：先发3块的情况下，剩下2块是不是就和发2块的方法一样了？

4：先发4块的情况下，剩下1块是不是就和发1块的方法一样了？

5：5块一次性发完，唯一方法

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

动态规划

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