資訊專欄INFORMATION COLUMN
摘要：題目曉萌希望將到的連續(xù)整數(shù)組成的集合劃分成兩個(gè)子集合，且保證每個(gè)集合的數(shù)字和是相等。輸出包括一行，僅一個(gè)整數(shù)，曉萌可以劃分對(duì)應(yīng)的集合的方案的個(gè)數(shù)。也就是本題可以轉(zhuǎn)化為部分和問(wèn)題，即前個(gè)數(shù)的和能湊成的有多少種。注意的是和為一種。
題目：曉萌希望將1到N的連續(xù)整數(shù)組成的集合劃分成兩個(gè)子集合，且保證每個(gè)集合的數(shù)字和是相等。例如，對(duì)于N=3，對(duì)應(yīng)的集合{1，2，3}能被劃分成{3} 和 {1,2}兩個(gè)子集合.
這兩個(gè)子集合中元素分別的和是相等的。
對(duì)于N=3，我們只有一種劃分方法，而對(duì)于N=7時(shí)，我們將有4種劃分的方案。
輸入包括一行，僅一個(gè)整數(shù)，表示N的值（1≤N≤39）。
輸出包括一行，僅一個(gè)整數(shù)，曉萌可以劃分對(duì)應(yīng)N的集合的方案的個(gè)數(shù)。當(dāng)沒(méi)發(fā)劃分時(shí)，輸出0。
樣例輸入
7
樣例輸出
4
分析： 劃分成兩部分，那么這兩部分的值也就是可以確定的，值為N! / 2。
所以N! 只有是偶數(shù)的話才可分。
也就是本題可以轉(zhuǎn)化為部分和問(wèn)題，即前N個(gè)數(shù)的和能湊成N! / 2的有多少種。
注意的是 {1, 2} {3}和{3} {1, 2}為一種。
設(shè) dp[i][j]前i個(gè)數(shù)的部分和可以湊成j的子集數(shù)
動(dòng)態(tài)轉(zhuǎn)移方程：
當(dāng)j >= arr[i - 1]時(shí) dp[i][j] = dp[i - 1][j - arr[i - 1]] + dp[i - 1][j]
其他： dp[i][j] = dp[i - 1][j]
代碼實(shí)例：
Scanner read = new Scanner(System.in);
int N = read.nextInt();
int sum = N * (N + 1)/ 2;
if((sum & 1) == 1)// 如果和為奇數(shù)時(shí) 不可分
System.out.println("0");
else{
// dp[i][j] 前i個(gè)數(shù)的部分和可以湊成j的子集數(shù)
long[][] dp = new long[N +1][(sum / 2) + 1];
//0可以湊成0
dp[0][0] = 1;
for(int i = 1; i <= N; ++i){
for(int j = 0; j <= sum / 2; ++j){
if(j >= i){//當(dāng)j >= arr[i - 1]時(shí) dp[i][j] = dp[i - 1][j - arr[i - 1]] + dp[i - 1][j];
dp[i][j] = dp[i - 1][j - i] + dp[i - 1][j];
}else{//其他： dp[i][j] = dp[i - 1][j];
dp[i][j] = dp[i - 1][j];
}
}
}
// 計(jì)數(shù)過(guò)程中類似的 {1, 2} {3}和{3} {1, 2} 會(huì)被重復(fù)記錄 所以除2
System.out.println(dp[N][sum / 2] / 2);
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/69416.html
摘要：代碼實(shí)現(xiàn)見(jiàn)下面評(píng)論對(duì)應(yīng)代碼動(dòng)態(tài)規(guī)劃基本思想和分治法基本思想有共同的地方，不同的是子問(wèn)題往往不是獨(dú)立的，有事母問(wèn)題要借助子問(wèn)題的解來(lái)判斷，因此把已經(jīng)計(jì)算好的問(wèn)題記錄在表格中，后續(xù)如果需要查詢一下，可以避免重復(fù)計(jì)算，這是動(dòng)態(tài)規(guī)劃的基本思想。 作者：心葉時(shí)間：2018-05-01 19:28 本文對(duì)應(yīng)github地址：https://github.com/yelloxing/... 以上實(shí)現(xiàn)...
摘要：如問(wèn)到是否使用某框架，實(shí)際是是問(wèn)該框架的使用場(chǎng)景，有什么特點(diǎn)，和同類可框架對(duì)比一系列的問(wèn)題。這兩個(gè)方向的區(qū)分點(diǎn)在于工作方向的側(cè)重點(diǎn)不同。 [TOC] 這是一份來(lái)自嗶哩嗶哩的Java面試Java面試 32個(gè)核心必考點(diǎn)完全解析（完） 課程預(yù)習(xí) 1.1 課程內(nèi)容分為三個(gè)模塊 基礎(chǔ)模塊： 技術(shù)崗位與面試 計(jì)算機(jī)基礎(chǔ) JVM原理 多線程 設(shè)計(jì)模式 數(shù)據(jù)結(jié)構(gòu)與算法 應(yīng)用模塊： 常用工具集 ...
摘要：動(dòng)態(tài)規(guī)劃問(wèn)題一定會(huì)具備最優(yōu)子結(jié)構(gòu)，才能通過(guò)子問(wèn)題的最值得到原問(wèn)題的最值。另外，雖然動(dòng)態(tài)規(guī)劃的核心思想就是窮舉求最值，但是問(wèn)題可以千變?nèi)f化，窮舉所有可行解其實(shí)并不是一件容易的事，只有列出正確的狀態(tài)轉(zhuǎn)移方程才能正確地窮舉。 大廠算法面試之leetcode精講3.動(dòng)態(tài)規(guī)劃視頻教程（高效學(xué)習(xí)）:點(diǎn)擊學(xué)習(xí)目錄：1.開篇介...
摘要：動(dòng)態(tài)規(guī)劃算法通?；谝粋€(gè)遞推公式及一個(gè)或多個(gè)初始狀態(tài)。動(dòng)態(tài)規(guī)劃有三個(gè)核心元素最優(yōu)子結(jié)構(gòu)邊界狀態(tài)轉(zhuǎn)移方程我們來(lái)看一到題目題目有一座高度是級(jí)臺(tái)階的樓梯，從下往上走，每跨一步只能向上級(jí)或者級(jí)臺(tái)階。 概念 動(dòng)態(tài)規(guī)劃(dynamic programming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過(guò)程(decision process)最優(yōu)化的數(shù)學(xué)方法。動(dòng)態(tài)規(guī)劃算法通?；谝粋€(gè)遞推公式及一個(gè)或多個(gè)初始狀態(tài)...
閱讀 3189·2021-11-24 10:24
閱讀 3039·2021-11-11 16:54
閱讀 3128·2021-09-22 15:55
閱讀 2062·2019-08-30 15:44
閱讀 1938·2019-08-29 18:41
閱讀 2794·2019-08-29 13:43
閱讀 3099·2019-08-29 12:51
閱讀 1256·2019-08-26 12:19
