深入分析區(qū)間型動態(tài)規(guī)劃

1、深入分析區(qū)間型動態(tài)規(guī)劃鄭州市第九中學(xué)張旭祥區(qū)間型動態(tài)規(guī)劃在信息學(xué)競賽中應(yīng)用甚廣，它是動態(tài)規(guī)劃中的經(jīng)典問題，最小代價字母樹是這類動態(tài)規(guī)劃最經(jīng)典的體現(xiàn)，對于初學(xué)者而言這類動態(tài)規(guī)劃并不太好理解。于是，區(qū)間型動態(tài)規(guī)劃又成了動態(tài)規(guī)劃中的難點問題。下面，本文將為大家深入分析區(qū)間型動態(tài)規(guī)劃的思想及其程序的實現(xiàn)，希望能對大家有所幫助。?歷屆大賽中區(qū)間型動態(tài)規(guī)劃題目的考查。區(qū)間型動態(tài)規(guī)劃是各大信息競賽出題的熱點，具體體現(xiàn)在以下題目：1.合并石子NOI19

2、952.能量項鏈NOIP20063.加分二叉樹NOIP20034.最優(yōu)排序二叉樹CTSC96這些題目出現(xiàn)的頻次及其所在比賽的重要性足以說明區(qū)間型動態(tài)規(guī)劃在各類動態(tài)規(guī)劃中有著舉足輕重的地位。二、區(qū)間型動態(tài)規(guī)劃的算法分析在這里就以經(jīng)典的最小代價字母樹作為例子，對區(qū)間型動態(tài)規(guī)劃的算法進行分析。問題描述：給定一個序列，如4、1、2、3我們將他們相加進行合并，最終合并成一個數(shù)，每次相加的代價是兩個加數(shù)的和，求怎樣的相加順序可以使總代價最小。很多初

3、學(xué)者認(rèn)為這類動態(tài)規(guī)劃不易理解，其重要原因是這類動態(tài)規(guī)劃與其他動態(tài)規(guī)劃的思想不大相同，而初學(xué)者又是利用其他動態(tài)規(guī)劃的思想來解決這類動態(tài)規(guī)劃，從而進入了思維誤區(qū)。這種錯誤的思維模式一旦建立便很難重新建立正確的解題思想，從而陷入絕境。這類動態(tài)規(guī)劃正確的解法是這樣的：首先，根據(jù)動態(tài)規(guī)劃無后效性的性質(zhì)可以想到：對于一個序列：A1、A2……An，假如最后相加的兩個數(shù)是第一個數(shù)到第i個數(shù)的和S[1i]以及第i1個數(shù)到第n個數(shù)的和S[i1n]，另外，對

4、于第一個數(shù)到第i個數(shù)相加的最小代價是F[1i]以及從第i1到第n個數(shù)相加的最小代價為F[i1n]，則總代價即為F[i1n]F[1i](前面相加的最小代價)S[1i]S[i1n]（最后一次相加的最小代價）。由此，我們可以清楚的看出要想求出總代價的最小值只要枚舉i的位置，使得F[i1n]F[1i]S[1i]S[i1n]的和最小即可。綜上所述我們可以總結(jié)出狀態(tài)轉(zhuǎn)移方程：輸入:44594輸出:4594859139224594414441822這