對于電路布線問題，想必學過動態(tài)規(guī)劃的大家都很清除。今天就來講解一下這個動態(tài)規(guī)劃經(jīng)典題目。

問題描述

在一塊電路板的上、下2端分別有n個接線柱。根據(jù)電路設計，要求用導 線(i,π(i))將上端接線柱與下端接線柱相連，如圖所示。其中π(i)是 {1,2,…,n}的一個排列。導線(i,π(i))稱為該電路板上的第i條連線。對于任 何1≤i<j≤n，第i條連線和第j條連線相交的充分且必要的條件是π(i)>π(j)。 電路布線問題要確定將哪些連線安排在第一層上，使得該層上有盡可能 多的連線。換句話說，該問題要求確定導線集Nets={(i,π(i)),1≤i≤n}的最 大不相交子集。

輸入

兩行輸入
第一行是一排接線柱的個數(shù)
第二行是上接線柱對應的下接線柱位置，即下文的p(i)
對于上圖輸入就是
10
3 1 2 4 7 9 5 6 10 8

分析

那么什么是最大不相交子集呢。咱們來一個一個字 的 扣含義。
首先最大就是字面意思最大的，最多的。
其次不相交也是字面意思，就是單純的兩條線不能有交點。
最后子集的定義是如果集合A的任意一個元素都是集合B的元素，那么集合A稱為集合B的子集（通俗點說就是在給出的導線集合里面，挑選幾條導線，這挑選的導線組成的集合就是子集）。
那么組合起來說的就是，在現(xiàn)有的線中挑選數(shù)量最多的導線且它們還不相交

我們發(fā)現(xiàn)這個題，好像不能從考慮最后一個步驟來推導了，我們好像還真不太好找出最后一個問題是什么。那么我們就換一種思路，回想以前的動態(tài)規(guī)劃好像都是在數(shù)組中記錄數(shù)值，供以后使用的而且都是一行一行的計算子問題。那我們先定義一個數(shù)組，考慮到有上下兩排線，那就定義二維數(shù)組吧.。
設dp[i][j]表示前i個上接線柱和前j個下接線柱組成的問題的最優(yōu)解包含的導線的數(shù)量(即前i個上接線柱和前j個下接線柱組成的集合的最大不相交子集中包含的導線數(shù))

為了方便說明再來定義一些規(guī)則：
上接線柱集合（1，2，3，4…n）
下接線柱集合（p(1),p(2),p(3),p(4)…p(n)）
p(n)代表上層接線柱n對應的下層接線柱的編號。例如下圖中上接線柱1，p(1)就是3

接下來以上圖為例先從第一行來看，來找一下規(guī)律觸發(fā)一下靈感
(第1步) i=1，j=1

(第2步) i=1，j=2

(第3步) i=1，j=3

唉突然發(fā)現(xiàn)此時，增加了一個，那就來想一想是什么原因讓他增加的呢。我們發(fā)現(xiàn)當j>=p(1)時他就增加了，接下來繼續(xù)看。
(第4步) i=1，j=3

然后類似的一直到 j==10 的時候
… …

(第10步) i=1，j=10

發(fā)現(xiàn)第一行除了j==3的時候增加了一個，其他的j>=p(1)的情況并沒有增加為什么會這樣呢？思考一下。因為我們的i是等于1的所以我們的dp[1][j]他最多只有一條線，我們上接線柱只包含了一個，所以他只能是小于等于一的數(shù)

這就給我們一個靈感我們可以根據(jù)i,p(i)的關系進行動態(tài)規(guī)劃列出可能的情況加以分析

1.考慮當 i =1的時候
（1）j<p(i):肯定是零
（2）j>=p(i):他也肯定是一，因為這時最優(yōu)解里面是空的，不用考慮香蕉🍌 （相交）的情況
2.考慮當 i>1時
（1）j<p(i):這時肯定還是不能包含這一條導線的，因為這一條導線的下接線柱沒有被包含前 j 個里面。
那么這時他就相當于dp[i-1][j]。 為什么這么說呢？因為在j<p(i)時這一條導線是不可能被包含在我們的最優(yōu)解里面的，所以就相當與這一條導線（i 導線）對于我們的當前的解是沒有任何作用的。他就相當于是前 i -1個上接線柱和前 j 個下接線柱構成的問題的最優(yōu)解。
也許此時聰明好學的你會問那為什么不是dp[i-1][j-1]呢？（即為什么不是前 i -1個上接線柱和前 j -1 個下接線柱構成的問題的最優(yōu)解呢？。）
此時我們直接舉一個一針見血的例子，如果i-1的下接線柱是 j 呢？dp[i-1][j-1]是不是就把第i-1條導線給漏掉了。
（2）j>=p(i): 這時候就說明我們可以包含這個導線，注意我說的是可以包含而不是一定包含。那么包含的條件是什么呢？想必你肯定已經(jīng)知道了，就是當這條導線與最優(yōu)解里面的導線都不香蕉🍌的時候 且 包含這個導線的最優(yōu)解的個數(shù)比不包含這條導線的個數(shù)要大的時候才會包含 （dp[i][j]=Math.max(dp[i-1][p[i]-1]+1,dp[i-1][j])） 。而相交的時候就不可以包含了（dp[i][j]=dp[i-1][j]）。

最優(yōu)子結(jié)構

1.對與i<1的時候肯定是滿足的，因為他的子問題不就是空的集合嗎。
2.對于i>1的時候
（1）j<p(i) 它的最優(yōu)解所包含的導線個數(shù)是是子問題的最優(yōu)解dp[i-1][j]。假設子問題的最優(yōu)解不是dp[i-1][j]而是R那么R>dp[i-1][j]所以原問題的最優(yōu)解應該是R，這就矛盾了。
（2）j>=p(i) 的時候他的子問題是選擇這一條導線（dp[i-1][p[i]-1]+1）或則不選這一條導線（dp[i][j]=dp[i-1][j]）這兩個中的最大值。對于不選擇和上面的證明是一樣的。
這里證明一下選擇的情況：
在證明之前先了解一下子問題為什么是這個集合（前i-1個上接線柱，前p[i]-1個下接線柱）而不是其他的集合（例如前i-1個上接線柱，前j個下接線柱）。
我們既然選擇了這一個導線就說明這個導線是不會與最優(yōu)解里面的導線相交的。dp[i-1][p[i]-1]是前i-1個上接線柱，前p[i]-1個下接線柱 組成的解。我們的這一條導線對應的接線柱是i和p[i]。i>i-1且p[i]>p[i]-1所以他是這個集合中的最后一條線。就好比上圖中的前4條導線，4是最后一條所以他肯定不
會與前三條相交的。

**那又為什么是j-1呢而不是其他的呢？**因為上接線柱是前i-1條，那么就算下接線柱不是j-1是j+1那么是不是就相交了呢
差不多理解了，就來證明最優(yōu)子結(jié)構：
如果dp[i-1][p[i]-1]不是子問題的最優(yōu)，最優(yōu)的是R那么R+1>dp[i-1][p[i]-1]+1,所以由子問題構成的原問題的最優(yōu)解應該是R+1而不是dp[i-1][p[i]-1]

代碼

import java.util.Scanner;public class AD {public static void MSN(int n,int[] p,int[][] dp){for(int i=1;i<=n;i++){for (int j=1;j<=n;j++){if(i<=1){if(j<p[i]){dp[i][j]=dp[i-1][j];}else {dp[i][j]=1;}}else {if(j<p[i]){dp[i][j]=dp[i-1][j];}else {dp[i][j]=Math.max(dp[i-1][p[i]-1]+1,dp[i-1][j]);}}}}
}public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int n=scanner.nextInt();int[] p=new int[n+1];p[0]=0;for(int i=1;i<=n;i++){p[i]=scanner.nextInt();}int[][] dp=new int[n+1][n+1];//        System.out.println(dp[n][n]);MSN(n,p,dp);System.out.println(dp[n][n]);}
}