让我们先来看看这道题目的描述
这道题目，我们第一反应就是动态规划，因为是求方案数，而不是求具体方案，所以确定方法为dp，但是怎么确定维数呢？我们可以先写一个递归版本的，再确定维数，顺便看看递归能否ac
classSolution{intcount=0;publicintprofitableSchemes(intn,intminProfit,int[]group,int[]profit){//回溯backtrace(profit,group,n,minProfit,0,0,0);returncount;}privatevoidbacktrace(int[]profit,int[]group,intn,intminProfit,intindex,intcurPerson,intcurProfit){if(index==group.length
curPersonn){if(curPerson=ncurProfit=minProfit)count++;return;}//跳过backtrace(profit,group,n,minProfit,index+1,curPerson,curProfit);backtrace(profit,group,n,minProfit,index+1,curPerson+group[index],curProfit+profit[index]);}}
提交发现，TLE
但是我们可以分析出来，维度有三个，工作数，参与的人数以及获得的利润，所以这道题目可以写成一个三维dp
对于每一个dp[j][k]既可以选择第i-1项工作也可以不选，但是只有当满足一定条件时才能选择，这个条件就是
j=group[i-1];
classSolution{publicintprofitableSchemes(intn,intminProfit,int[]group,int[]profit){//把递归改成dpintG=group.length;int[][][]dp=newint[G+1][n+1][minProfit+1];//表示前i项工作选了j人工作，利润至少k的个数dp[0][0][0]=1;for(inti=1;i=G;++i){for(intj=0;j=n;++j){for(intk=0;k=minProfit;++k){//不选dp[j][k]=dp[i-1][j][k];//可以选if(j=group[i-1]){dp[j][k]=(dp[j][k]+dp[i-1][j-group[i-1]][Math.max(0,k-profit[i-1])])%;}}}}intcount=0;for(intj=0;j=n;++j){count=(count+dp[G][j][minProfit])%;}returncount;}}
这道题目还有一个坑的点就是要注意对dp[j][k]取模1e9+7，否则会卡在某个测试用例
经过观察我们还可以发现，dp[][]只能由dp[i-1][][]得到
这说明这个三维dp是可以将到二维的，在这里就不放二维的版本了～
晚点可以试试二维的做法～
预览时标签不可点收录于话题#个上一篇下一篇