有趣的劃分問題

04-17

最近做到一些劃分問題的題目,同時結合之前學到的問題

1.集合的劃分-第二類斯特林數

含有 $n$ 個元素的集合劃分成 $k$ 個的數量,我們記作 $left{ n,k ight}$ .

比如 $left{ 1,2,3 ight}$ 劃分兩個,有 $left{ 1,2 ight}cupleft{ 3 ight},left{ 1,3 ight}cupleft{ 2 ight},left{ 3,2 ight}cupleft{ 1 ight}$ 三種情況

那麼考慮遞推關係,提取這個集合隨便一個元素這個元素的位置要麼是單獨的一個,要麼插入到別的劃分中,那麼就有 $left{ n,k ight}=(k-1)left{ n-1,k ight}+left{ n-1,k-1 ight}$

2.集合的輪換-第一類斯特林數

輪換是環形隊列比如1->2->3->1,那麼我們含有 $n$ 個元素的集合劃分成 $k$ 個輪換的數量記作 $left[ n,k ight]$ .

那麼遞推關係就是,提取這個集合隨便一個元素這個元素要麼就在自己單獨一個輪換中,要麼就在其它 $n-1$ 個元素的輪換中.對於後面一種情形,考慮的就是對於一個固定的輪換形式比如 $left[ A,B,C ight]left[ D,E,F ight]$ 可以插入到6個位置中形成6個新的輪換.也就是說 $n-1$ 個元素的輪換插入一個新的元素總共會生成 $n-1$ 個輪換.所以有

$left[ n,k ight]=(n-1)left[ n-1,k ight]+left[ n-1,k-1 ight]$

3.數的劃分

一個數 $m$ 可以劃分成 $k$ 個整數,有 $m_{1}+....+m_{k}=m,0<=m_{1}<=m_{2}<=....<=m_{k}$ ,問有多少種情況.我們可以將這個值記作 $H(m,k)$ ,那麼就有兩個情況

①所有劃分的數都大於0,這時 $H1=H(m-k,k)$

②劃分中的數有0,這時可以去掉一個含有0的劃分,使得劃分減一 $H2=H(m,k-1)$ 所以遞推關係有

$H(m,k)=H1+H2=H(m-k,k)+H(m,k-1)$

(注:如果說要讓劃分都大於0,那麼數m劃分成k個有 $H(m-k,k)$ 種情況)

4.數組的劃分

具體由這道題來講(分割數組的最大值 - LeetCode (中國)),題目如下

給定一個非負整數數組和一個整數 m，你需要將這個數組分成 m 個非空的連續子數組。設計一個演算法使得這 m 個子數組各自和的最大值最小.

注意:

數組長度 n 滿足以下條件:

1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)

那麼就是遍歷所有小一的劃分,有

$dp[n][k]=min(max(dp[n-i][k-1],(sum[n]-sum[n-i]))(k-1<i<n))$

代碼如下

int splitArray(vector<int>& nums, int m) { int dp[53][1007]; int sum[1007]; int len = nums.size(); dp[1][1] = nums[0]; sum[1] = dp[1][1]; for(int i=2;i<=len;i++){ dp[1][i] = dp[1][i-1]+nums[i-1]; sum[i] = dp[1][i]; } for(int i=2;i<=m;i++){ for(int j=i;j<=len;j++){ int Min = INT_MAX; for(int h=i;h<=j;h++){ int c = max(dp[i-1][h-1],sum[j]-sum[h-1]); if(Min>c){ Min=c; } } dp[i][j]=Min; } } return dp[m][len]; }