一、题意简述
这道题要使用 DFS 来解题。
Q:DFS 有哪些参数?
A:
1、花摆到了第几种?
2、摆了多少盆花?
二、求什么?
求方案总数
三、深搜的步骤:
1、查看是否应该终止 (花摆的盆数≥m)
2、递归所有可能的方案 (0~)
(若要记忆化搜索,只用加上提前 return 记忆的答案或 0 部分和存储部分即可)
三、复杂度
普通 DFS(30 分)
时间复杂度:O()
空间复杂度:S()
记忆化搜索 DFS(100 分)
时间复杂度:O(✕✕)
空间复杂度:S()
四、代码
30分:
#include <bits/stdc++.h>
using namespace std;
int n,m,a[105],ans = 0;
void dfs(int i,int sum){
if(sum == m){
ans = (ans + 1) % 1000007;
return ;
}else if(sum > m){
return ;
}
if(i > n)return ;
for(int j = 0;j <= a[i];j++){
dfs(i + 1,sum + j);
if(sum + j > m)break;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int j = 1;j <= n;j++)scanf("%d",&a[j]);
dfs(1,0);
printf("%d",ans % 1000007);
return 0;
}
100分:
#include <bits/stdc++.h>
using namespace std;
int n,m,a[105],form[105][105];
int dfs(int i,int sum){
if(sum == m)return 1;
if(sum > m)return 0;
if(i > n)return 0;
if(form[i][sum] != 0)return form[i][sum];
int ans = 0;
for(int j = 0;j <= a[i];j++)ans = (ans + dfs(i + 1,sum + j)) % 1000007;
form[i][sum] = ans;
return ans;
}
int main(){
memset(a,0,sizeof(a));
memset(form,0,sizeof(form));
scanf("%d%d",&n,&m);
for(int j = 1;j <= n;j++)scanf("%d",&a[j]);
printf("%d",dfs(1,0) % 1000007);
return 0;
}
浏览次数: