题目描述

小R不再追求甜点中最高的喜爱值，今天他想要的是甜点喜爱值之和正好匹配他的预期值 S。为了达到这个目标，他可以使用魔法棒来改变甜点的喜爱值，使其变为原来喜爱值的阶乘。每个甜点只能使用一次魔法棒，也可以完全不用。

下午茶小哥今天带来了 N 个甜点，每个甜点都有一个固定的喜爱值。小R有 M 个魔法棒，他可以选择任意甜点使用，但每个甜点只能使用一次魔法棒。他的目标是通过选择一些甜点，可能使用魔法棒，使得这些甜点的喜爱值之和恰好为 S。

请计算小R有多少种不同的方案满足他的要求。如果两种方案中，选择的甜点不同，或者使用魔法棒的甜点不同，则视为不同的方案。

样例

样例1：

输入：n = 3, m = 2, s = 6, like = [1, 2, 3]
输出：5

样例2：

输入：n = 3, m = 1, s = 1, like = [1, 1, 1]
输出：6

样例3：

输入：n = 5, m = 3, s = 24, like = [1, 2, 3, 4, 5]
输出：1

样例4：

输入：n = 4, m = 0, s = 10, like = [1, 3, 3, 3]
输出：1

样例5：

输入：n = 6, m = 1, s = 35, like = [5, 5, 5, 5, 5, 5]
输出：0

算法1

(dp)

public class Main {
    public static int solution(int n, int m, int s, int[] like) {
        int dp[][][]= new int [n+2][s+1][m+1];
      //  dp[n][s][m]  在0-n个物品中，有m次魔法机会,获得美味值为s的方案数目
      for(int i=0;i<=m;i++)  
      for(int j=0;j<=n;j++)
         dp[j][0][i]=1;



         int likes[] =  new int [like.length+1];
for(int i=0;i<like.length;i++)   likes[i+1]=like[i];//平移

      for (int i = 1; i <= n; i++) {
        for (int k= 0; k <=s; k++) {
          for (int j = 0; j <=m; j++) {

                dp[i][k][j]=dp[i-1][k][j]  ;
                if(k>=likes[i])  dp[i][k][j]+= dp[i-1][k-likes[i]][j];
                //限制  7之后的阶乘不需要计算
                if(j>=1&&likes[i]<=7&&k>=jiecheng(likes[i])){
                    dp[i][k][j]+=dp[i-1][k-jiecheng(likes[i])][j-1];
                }
            }
        }
      }
      //System.out.println( dp[n][s][m]);
        // Please write your code here
        return  dp[n][s][m];
    }
    public static int jiecheng(int x){
        int t=1;
        for(int i=1;i<=x;i++){
            t*=i;
        }
        return t;
    }

    public static void main(String[] args) {
        //  You can add more test cases here
        int[] like1 = {1, 2, 3};
        int[] like2 = {1, 1, 1};

        System.out.println(solution(3, 2, 6, like1) == 5);
        System.out.println(solution(3, 1, 1, like2) == 6);
    }
}
blablabla

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla