2018.01.01(數字三角形，最長上升子序列等)

2017.12.24

?簡單的動態規劃

1.數字三角形(算法引入)

題目描述：下圖所示是一個數字三角形，其中三角形中的數值為正整數，現規定從最頂層往下走到最底層，每一步可沿左斜線向下或右斜線向下走。設三角形有n層，編程計算出從頂層到底層的一條路徑，使得該路徑上的和最大，輸出最大值。(n<=100)

思路&&代碼(搜索回溯)：

最顯而易見的思路，既然要求一條最短的路徑，最簡單的方法就是遍歷所有的路徑，找到一條最優的。時間復雜度是O(2ⁿ)以下是搜索代碼。

#include <stdio.h>
#include <math.h>
#include <string.h>
int map[101][101],n;
int count=0,ans=-20180101;
void search(int x,int y){
　　count+=map[x][y];
　　if(x==n){
　　　　if(count>ans)ans=count;
　　}
　　else{
　　search(x+1,y+1);
　　search(x+1,y);
　　}
　　count-=map[x][y];
}
int main(){
　　scanf("%d",&n);
　　int i,j;
　　for(i=1;i<=n;i++){
　　　　for(j=1;j<=i;j++){
　　　　　　scanf("%d",&map[i][j]);
　　　　}
　　}
　　search(1,1);
　　printf("%d\n",ans);
　　return 0;
}

思路&&代碼(分治法)：

對于任意一個點，我們可以把它的最大值和看成Max(sum[i+1][j],[i+1][j+1])，分解為兩個規模更小的子問題。但是本質上和搜索沒有區別，所以時間復雜度還是O(2ⁿ)。

#include <stdio.h>
#include <math.h>
#include <string.h>
int n,map[101][101];
int fenzhi(int x,int y){
　　if(x==n)return map[x][y];
　　int zi1,zi2,_max;
　　zi1=fenzhi(x+1,y);
　　zi2=fenzhi(x+1,y+1);
　　if(zi1<=zi2)_max=zi2;
　　else           _max=zi1;
　　return _max+map[x][y];
}
int main(){
　　scanf("%d",&n);
　　int i,j;
　　for(i=1;i<=n;i++){
　　　　for(j=1;j<=i;j++){
　　　　　　scanf("%d",&map[i][j]);
　　　　}
　　}
　　printf("%d",fenzhi(1,1));
　　return 0;
}

思路&&代碼(記憶化)：

比搜索要更優。我們注意到，不管是搜索還是分治，它們都是O(2ⁿ)的時間復雜度，是因為它們算了一些重復的東西。既然有重復，那我就把這些重復算的東西用一個數組保存起來，要用時就不用再去算一遍，只要調用了。所以把時間復雜度大大提升了，只有O(n²)了。

#include <stdio.h>
#include <math.h>
#include <string.h>
int map[101][101],book[101][101];
int n;
int max(int x,int y){
　　if(y>x)
　　　　return y;
　　else
　　　　return x;
}
int search(int r,int c){
　　int ans;
　　if (r==n) return map[r][c];
　　if (book[r+1][c]==-1)
　　　　book[r+1][c]=search(r+1,c);
　　if (book[r+1][c+1]==-1)
　　　　book[r+1][c+1]=search(r+1,c+1);
　　ans=max(book[r+1][c],book[r+1][c+1])+book[r][c]; 
　　return ans;
}
int main(){
　　scanf("%d",&n);
　　int i,j;
　　for(i=1;i<=n;i++){
　　　　for(j=1;j<=i;j++){
　　　　　　scanf("%d",&map[i][j]);
　　　　　　book[i][j]=-1;
　　　　}
　　}
　　printf("%d",search(1,1));
　　return 0;
}

思路&&代碼(動態規劃)：

自底向上。第i層的任意一個點，其最大值是它自己加上它下一層的兩個點的最大值之和。用i表示行，j表示列，狀態轉移方程如下。這樣，時間復雜度也只有O(2ⁿ)。

#include <stdio.h>
#include <math.h>
#include <string.h>
int map[101][101],book[101][101];
int max(int x,int y){
　　if(x>y)return x;
　　else   return y;
}
int main(){
　　int n;
　　scanf("%d",&n);
　　int i,j;
　　for(i=1;i<=n;i++){
　　　　for(j=1;j<=i;j++){
　　　　　　scanf("%d",&map[i][j]);
　　　　}
　　}
　　for(j=1;j<=n;j++)
　　　　book[n][j]=map[n][j];
　　for(i=n-1;i>=1;i--)
　　　　for(j=1;j<=i;j++)
   　　　　　book[i][j]=max(book[i+1][j+1],book[i+1][j])+map[i][j];
　　　　　　　printf("%d",book[1][1]);
　　return 0;
}

2.最長上升子序列

思路：

對于以第i個數為右端點的一個序列，他本身就是一個長度為1的上升子序列。這時，如果它的右邊有比它數值更小的數，這時的最長上升子序列就是這個元素本身的長度1和以他前面的比他數值更小的這個元素為右端點的最長上升子序列的長度和。

狀態轉移方程：sum[i]=_Max(sum[i],sum[j]+1); ?(j<i，num[j]<num[i])

核心代碼：

sum[1]=1;
    for(i=2;i<=n;i++){
        sum[i]=1;
        for(j=1;j<i;j++){
            if(num[j]<num[i]){
                sum[i]=_Max(sum[i],sum[j]+1);
            }
        }
    }
    for(i=1;i<=n;i++)
        max=_Max(max,sum[i]);

狀態：AC