国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

動態(tài)規(guī)劃 解決部分和問題（java）

韓冰 / 1765人閱讀

摘要：題目曉萌希望將到的連續(xù)整數(shù)組成的集合劃分成兩個子集合，且保證每個集合的數(shù)字和是相等。輸出包括一行，僅一個整數(shù)，曉萌可以劃分對應(yīng)的集合的方案的個數(shù)。也就是本題可以轉(zhuǎn)化為部分和問題，即前個數(shù)的和能湊成的有多少種。注意的是和為一種。

題目：曉萌希望將1到N的連續(xù)整數(shù)組成的集合劃分成兩個子集合，且保證每個集合的數(shù)字和是相等。例如，對于N=3，對應(yīng)的集合{1，2，3}能被劃分成{3} 和 {1,2}兩個子集合.

這兩個子集合中元素分別的和是相等的。

對于N=3，我們只有一種劃分方法，而對于N=7時，我們將有4種劃分的方案。

輸入包括一行，僅一個整數(shù)，表示N的值（1≤N≤39）。

輸出包括一行，僅一個整數(shù)，曉萌可以劃分對應(yīng)N的集合的方案的個數(shù)。當(dāng)沒發(fā)劃分時，輸出0。

樣例輸入

7
樣例輸出

4

分析： 劃分成兩部分，那么這兩部分的值也就是可以確定的，值為N! / 2。

  所以N! 只有是偶數(shù)的話才可分。
  也就是本題可以轉(zhuǎn)化為部分和問題，即前N個數(shù)的和能湊成N! / 2的有多少種。
  注意的是 {1, 2} {3}和{3} {1, 2}為一種。
  設(shè) dp[i][j]前i個數(shù)的部分和可以湊成j的子集數(shù)
  動態(tài)轉(zhuǎn)移方程：
  當(dāng)j >= arr[i - 1]時 dp[i][j] = dp[i - 1][j - arr[i - 1]] + dp[i - 1][j]
  其他： dp[i][j] = dp[i - 1][j]

代碼實例：

        Scanner read = new Scanner(System.in);
        int N = read.nextInt();
        int sum = N * (N + 1)/ 2;
        if((sum & 1) == 1)// 如果和為奇數(shù)時  不可分
            System.out.println("0");
        else{
            // dp[i][j] 前i個數(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]時  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];
                    }
                }
            }
            // 計數(shù)過程中類似的  {1, 2} {3}和{3} {1, 2} 會被重復(fù)記錄 所以除2
            System.out.println(dp[N][sum / 2] / 2);
        }

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/69416.html

相關(guān)文章

  • 基本算法思想：遞歸+分治+動態(tài)規(guī)劃+貪心+回溯+分支限界

    摘要：代碼實現(xiàn)見下面評論對應(yīng)代碼動態(tài)規(guī)劃基本思想和分治法基本思想有共同的地方，不同的是子問題往往不是獨立的，有事母問題要借助子問題的解來判斷，因此把已經(jīng)計算好的問題記錄在表格中，后續(xù)如果需要查詢一下，可以避免重復(fù)計算，這是動態(tài)規(guī)劃的基本思想。 作者：心葉時間：2018-05-01 19:28 本文對應(yīng)github地址：https://github.com/yelloxing/... 以上實現(xiàn)...

    EscapedDog 評論0 收藏0

  • Java面試 32個核心必考點完全解析

    摘要：如問到是否使用某框架，實際是是問該框架的使用場景，有什么特點，和同類可框架對比一系列的問題。這兩個方向的區(qū)分點在于工作方向的側(cè)重點不同。 [TOC] 這是一份來自嗶哩嗶哩的Java面試Java面試 32個核心必考點完全解析（完） 課程預(yù)習(xí) 1.1 課程內(nèi)容分為三個模塊 基礎(chǔ)模塊： 技術(shù)崗位與面試 計算機(jī)基礎(chǔ) JVM原理 多線程 設(shè)計模式 數(shù)據(jù)結(jié)構(gòu)與算法 應(yīng)用模塊： 常用工具集 ...

    JiaXinYi 評論0 收藏0

  • 大廠算法面試之leetcode精講3.動態(tài)規(guī)劃

    摘要：動態(tài)規(guī)劃問題一定會具備最優(yōu)子結(jié)構(gòu)，才能通過子問題的最值得到原問題的最值。另外，雖然動態(tài)規(guī)劃的核心思想就是窮舉求最值，但是問題可以千變?nèi)f化，窮舉所有可行解其實并不是一件容易的事，只有列出正確的狀態(tài)轉(zhuǎn)移方程才能正確地窮舉。 大廠算法面試之leetcode精講3.動態(tài)規(guī)劃視頻教程（高效學(xué)習(xí)）:點擊學(xué)習(xí)目錄：1.開篇介...

    番茄西紅柿 評論0 收藏2637

  • 動態(tài)規(guī)劃入門（以爬樓梯為例）

    摘要：動態(tài)規(guī)劃算法通?；谝粋€遞推公式及一個或多個初始狀態(tài)。動態(tài)規(guī)劃有三個核心元素最優(yōu)子結(jié)構(gòu)邊界狀態(tài)轉(zhuǎn)移方程我們來看一到題目題目有一座高度是級臺階的樓梯，從下往上走，每跨一步只能向上級或者級臺階。 概念 動態(tài)規(guī)劃(dynamic programming)是運籌學(xué)的一個分支，是求解決策過程(decision process)最優(yōu)化的數(shù)學(xué)方法。動態(tài)規(guī)劃算法通?；谝粋€遞推公式及一個或多個初始狀態(tài)...

    cyixlq 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<