这道题可以用dfs吗？~~（不会建议学~~
by Katz @ 2022-09-21 18:20:29
@[caoshurui](/user/677234) 那么有没有一种可能，dp之所以存在是因为 dfs 无法在给定的时间限制内解决所有问题。
by Error_Eric @ 2022-09-21 18:25:02
@[Error_Eric](/user/217300) 呵呵
by caoshurui @ 2022-09-21 18:27:18
@[caoshurui](/user/677234) DP 其实很容易理解，可以理解成 DFS 的记忆化剪枝，因为有很多相同的状态在 DFS 的过程中会重复访问到。
by Tx_Lcy @ 2022-09-21 18:49:08
有些人发个“呵呵”到底是什么意思？有点无法理解
by Katz @ 2022-09-21 19:31:41
谢谢各位大佬
by caoshurui @ 2022-09-22 12:47:00
考古
~~其实加个记忆化就过了~~
```cpp
#include<bits/stdc++.h>
using namespace std;
bool jyh[15][1005];
int a[15];
bool l[1005];
int x[10]={0,1,2,3,5,10,20},ans;
void dfs(int step,int sum){
if(jyh[step][sum])return;
jyh[step][sum]=1;
if(step>6){
if(!l[sum]&&sum)ans++;
l[sum]=1;
return;
}
for(int i=1;i<=a[step];i++)dfs(step+1,sum+x[step]*i);
dfs(step+1,sum);
}
int main(){
for(int i=1;i<=6;i++)cin>>a[i];
dfs(1,0);
cout<<"Total="<<ans;
}
```
而且还超快
by zzy_2013xnkl @ 2022-11-12 13:53:36
@[caoshurui](/user/677234) 考古，~~不会dp的dp巨佬~~
by Yun_Mengxi @ 2023-08-01 11:06:55
@[Yun_Mengxi](/user/758416) 这都快一年了。。。
by caoshurui @ 2023-08-01 11:12:33