9.13 美团软开题目

贴一下我做的dp的答案把 while(sc.hasNext()){             n=sc.nextInt();             k=sc.nextInt();             d=sc.nextInt();             ans=0;             /*backtrack(0,0);             System.out.println(ans);*/             int[][] dp=new int[n+1][2];             for (int i = 0; i < d; i++) {                 dp[i][1]=0;             }             dp[1][0]=1;             dp[0][0]=1;             for (int i = 2; i <= n; i++) {                 for (int j = 1; j <= k; j++) {                     if(i-j<0)continue;                     if(j<d) {                         dp[i][0]+=dp[i-j][0];                         dp[i][1] += dp[i - j][1];                     }                     else {                         dp[i][1] +=dp[i - j][1] + dp[i - j][0];                     }                 }             }             System.out.println(dp[n][1]);         }

看起来像个dp啊。 考虑dp[S][0/1]表示拼成S的时候是否使用了超过d的数，然后考虑状态转移即可。 时间复杂度是O(N*K)的。

我看到有dfs剪枝不超时的，用的java

用两个dp数组或者一个二维的数组，计算不含大于等于d的方案数量和含有大于等于d的方案数量

import java.util.*; public class Main {  static int count=0;  public static void main(String[] args) {  Scanner sc=new Scanner(System.in);  while(sc.hasNext()) {      int n=sc.nextInt();  int k=sc.nextInt();  int d=sc.nextInt();  gg(n,d,0,k,0);  System.out.println(count);  }    }  public static void gg(int n,int d,int sum,int index,int max) {  if(n==sum) {    if(max>=d){ count++;        }  return;  }  int t=max;  for(int i=index;i>=1;i--) {  if(sum+i>n) {  continue;  }  if(i>max) {     max=i;  }  gg(n,d,sum+i,index,max);  max=t;    }    } }

'只适用于Python，过了本地测试&(10111)#39; n, k, d = [int(i) for i in input().strip().split(' &(5528)#39;)] res = [] count = 0 ' 排列&#39; def A(n, m):     res = 1     for i in range(m, m-n, -1):         res *= i     return res '计算数组有多少种排列组合&(10110)#39; def c(arr):     a_dict = {}     for i in arr:         if i in a_dict.keys():             a_dict[i] += 1         else:             a_dict[i] = 1     l = len(arr)     res = A(l, l)     for i in a_dict.values():         res //= A(i, i)     return res " 依次获取所有的组合，但没有排列，用函数c计算每种有多少种排列" def f(rest, start, res):     global count     for i in range(start, rest+1):         if rest == i:             count = (count+c(res+[i])) % 998244353         if i == res[0]:             break         f3(rest-i, start=i, res=res+[i]) for i in range(d, k+1):     f3(n-i, 1, res=[i]) print(count)