DFS（深度優(yōu)先搜索） 比較暴力功利，大意是將某一個(gè)狀態(tài)開(kāi)始不斷轉(zhuǎn)移到下一個(gè)狀態(tài)，直到不能轉(zhuǎn)移，然后退回到前一個(gè)分枝的另一個(gè)下一個(gè)狀態(tài)以此類(lèi)推，直到找到最終的解
心得：找到終止條件和分支的條件
例題：從N個(gè)數(shù)中找到其中的幾個(gè)數(shù)使他們的和恰好為K
#include<iostream>#define maxn 10000using namespace std;int a[maxn];int n,k;bool dfs(int i,int sum){ if(i==n) return sum==k; //終止條件 if(dfs(i+1,sum)) return true; //分支條件 else if(dfs(i+1,sum+a[i])) return true; return false;}int main(){ cin>>n; for(int i=0;i<n;i++) cin>>a[i]; cin>>k; if(dfs(0,0)) cout<<"yes"<<endl; else cout<<"no"<<endl; return 0;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
