算法——动态规划

1 数塔问题

找出一条最大的路径(图片来自百度）

#include<stdio.h>
#include<string.h>

int main(){
    int n;
    scanf("%d",&n);
    int arr[50][50];
    memset(arr, 0, sizeof(arr));
    int i,j=1;
    for(i=1;i<=n;i++) 
        for(j=1;j<=i;j++)
            scanf("%d",&arr[i][j]);

    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++)
        if(arr[i-1][j-1]>=arr[i-1][j]){
            arr[i][j]+=arr[i-1][j-1];
        }
        else arr[i][j]+=arr[i-1][j];
    }
    int m=0;
    for(j=1;j<=n;j++)
        if(arr[n][j]>m)
            m=arr[n][j];
    printf("%d",m);
    return 0;
} 

2 LIS 最大上升子数列

#include<stdio.h>
#include<string.h>
int main(){
    int n,t=0;
    scanf("%d",&n);
    int arr[n];
    int arr1[n];
    memset(arr1,0,sizeof(arr1));
    for(int i=0;i<n;i++)
        scanf("%d",&arr[i]);  
    for(int i=0;i<n;i++){
        arr1[i]=1;
        for(int j=0;j<i;j++)
            if(arr[i]>arr[j])
                if((arr1[j]+1)>arr1[i])
                    arr1[i]=arr1[j]+1;
    }
    for(int i=0;i<n;i++)
        if(arr1[i]>t) t=arr1[i];
    printf("%d",t);
    return 0;
    }