數(shù)的劃分（題目鏈接）

思路

• 使用遞歸做的類似多重for循環(huán)的搜索

代碼

#include <iostream>
using namespace std;

int n, k, ans = 0;

/*
 *last:上一次循環(huán)到的值
 *cur :當(dāng)前分的個數(shù)
 *sum :當(dāng)前累計的總數(shù)
*/
void f(int last, int cur, int sum){
    if(cur == k){           //如果分的個數(shù)和需要分的個數(shù)相同，就退出 
        if(n == sum){       //如果剛剛分完，就統(tǒng)計一次 
            ans++;
        }
        return;
    }
    //限制數(shù)范圍，防止后面分的數(shù)比前面的小，從而避免重復(fù) 
    for(int i = last; sum + i*(k-cur) <= n; i++){
        f(i, cur+1, sum+i);
    }
}

int main(){
    cin >> n >> k;
    f(1, 0, 0);
    cout << ans;

    return 0;
} 
/*
 *最開始想到的方法是dp，但是最開始找到的狀態(tài)轉(zhuǎn)移方程有問題，所以沒能AC， 
 *后面自己也想到了用多層for來搜索，搜索的次數(shù)用遞歸解決，但是循環(huán)條件
 *沒有找好，導(dǎo)致分出來的數(shù)有重復(fù)，沒有AC；看了dalao的方法，才知道了循環(huán)
 *條件，最終AC。 
*/