65
技術社區[雲棲]
poj 1163 The Triangle【dp】
和POJ3176幾乎一模一樣，（隻有row的範圍不同，其實可以不用改的，我還是改了一下），連給的數據都一樣，都是最簡單的那個 dp 動歸問題
AC的代碼：
#include<stdio.h>
int dp[102][102];
inline int max(int a,int b){return a>b?a:b;}
int main()
{
int n,i,j;
scanf("%d",&n);
//輸入
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
scanf("%d",&dp[i][j]);
//dp
for(i=n-1;i>=1;i--)
for(j=1;j<=i;j++)
dp[i][j]=max(dp[i][j]+dp[i+1][j],dp[i][j]+dp[i+1][j+1]);
printf("%d\n",dp[1][1]);
return 0;
}
轉過來一個寫的還不錯的貼
問題描述：輸入一個數字三角形
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
(Figure 1)
如Figure 1所示一樣，在上麵的數字三角形中尋找一條從頂部到底邊的路徑，使得路徑上所經過的數字之和最大。路徑上的每一步都是能往左下或右下走。隻需要求出最的和即可，不需要輸出路徑。
解題思路：算法一 、遞歸思想
設f(i,j) 為三角形上從點(i,j)出發向下走的最長路經，則 f(i,j) =max(f(i 1,j), f(i 1,j 1))
要輸出的就是f(0,0)即從最上麵一點出發的最長路經。
以D(r, j)表示第r行第 j 個數字，以MaxSum(r, j) 代表從第 r 行的第 j 個數字到底邊的各條路徑中，數字之和最大的那條路徑的數字之和，則本題是要求MaxSum(0,0)。（假設行編號和一行內數字編號都從0開始)。
典型的動態規劃問題。
從某個D(r, j)出發，顯然下一步隻能走D(r 1,j)或者D(r 1, j 1)，所以，對於N行的三角形：
if ( r == N-1 )
MaxSum(r,j) = D(N-1,j)
else
MaxSum(r, j) = Max(MaxSum(r 1,j),MaxSum(r 1,j 1) ) D(r,j);
代碼如下：
#include <iostream.h>
#define MAX 101
int triangle[MAX][MAX];
int n;
int longestPath(int i, int j);
void main(){
int i,j;
cin >>n;
for(i=0;i<n;i)
for(j=0;j<=i;j )
cin>> triangle[i][j];
cout <<longestPath(0,0) << endl;
}
int longestPath(int i, int j){
if(i==n-1)return triangle[i][j];
int x =longestPath(i 1,j);
int y =longestPath(i 1,j 1);
if(x<y) x=y;
return x triangle[i][j];
}
（超時！！！！）
為什麼會超時呢？
答：如果采用遞規的方法，深度遍曆每條路徑，存在大量重複計算，則時間複雜度為 2n，對於 n = 100，肯定超時。
一種可能的改進思想：從下往上計算，對於每一點，隻需要保留從下麵來的路徑中和最大的路徑的和即可。
因為在它上麵的點隻關心到達它的最大路徑和，不關心它從那條路經上來的。
問題：有幾種解法？？
從使用不同的存儲開銷角度分析
2?00?00譻izeof(int)
(100?00 100)譻izeof(int)
100譻izeof(int)
解法一、
如果每算出一個MaxSum(r,j)就保存起來，則可以用o(n2)時間完成計算。因為三角形的數字總數是n(n 1)/2
此時需要的存儲空間是：
int D[100][100]; //用於存儲三角形中的數字
int Sum[100][100]; //用於存儲每個MaxSum(r,j)
解法二、
沒必要用二維Sum數組存儲每一個MaxSum(r,j),隻要從底層一行行向上遞推，那麼隻要一維數組Sum[100]即可,即隻要存儲一行的MaxSum值就可以。比解法一改進之處在於節省空間，時間複雜度不變。
解法三、
能否不用二維數組D[100][100]存儲數字呢？
思路：倒過來考慮。前麵的思路是從底往上最終算出MaxSum(0,0)。如果從頂往下算，最終算出每一個MaxSum(N-1,j)，然後再取最大的MaxSum(N-1,j)，不就是答案嗎？此時遞推公式為：
if( r == 0 )
MaxSum(r,j) = D[0][0];
else
MaxSum(r,j) = Max(MaxSum(r-1,j-1), MaxSum(r-1,j)) D[r][j];
由於兩重循環形式為：
for( r = 0 ; r < N ; r )
for( j = 0 ; j < r 1 ; j ) {
………..
}
r,j不斷遞增，所以實際上不需要D[100][100]數組，每次從文件裏讀取下一個數字即可。
而每一行的每個MaxSum(r,j)仍然都需要存儲起來，這樣，隻需要一個Sum[100]數組。
(注：隻需設一個臨時存儲變量，在計算MaxSum(r,j)後寫入數組時，暫存MaxSum(r-1,j))
解法四：
也就是本人所執行的算法，它是基於解法三中“從上往下”的思想，每輸入一個數後臨時存起來，然後用一個sum[i]來存放該處的最大路徑和數，由於所輸入的數字三角是成一個以1為公差的等差數列，充分利用其變量間的一種親密關係，成功實現並不困難。具體的算法如下：
#include <iostream>
using namespace std;
int main(){
int sum[5051]={0}; //聲明用來存放數據的數組，sum=(n^2+n)/2 max(sum)=5050(n==100)
int n,r,j,num,i=1,max=0; //r表變化的行數，
cin>>n; //輸入數據行數
for(r=1;r<=n;r++){
for(j=1;j<=r;j++,i++){
scanf("%d",&num); //輸入三角形數據
if(j==1){sum[i]=num+sum[i-r+1];continue;} //輸入的是每行的第一個數
if(j==r)sum[i]=num+sum[i-r]; //輸入的是每行中的最後一個數
else sum[i]=(sum[i-r]>sum[i-r+1]?sum[i-r]:sum[i-r+1])+num; //輸入的是中間數時
}
}
/*for(j=1;j<i;j++)cout<<sum[j]<<""; //測試用來輸出每個點上所對應的最大路徑和數
cout<<endl;
*/
for(j=1;j<i;j++) //尋最大路徑和數
if(sum[j]>max)max=sum[j];
cout<<max<<endl;
system("pause");
return 0;
}
心得：經過解此題，讓我走出了一個算法的局限誤區，思維進一步得到了提高，之前遇到一個類似的題，當初就受思維的局限心想要用到搜索，或者是有關圖的遍曆才能解決的問題，沒想到如今卻隻要區區幾十行代碼就解決了。“規律往往是掌握在有一雙“狠”的眼睛的人的大腦裏！”從而得出了這樣一句話來收場。
最後更新：2017-04-03 14:53:41