DP练习代码

1.最长递增子串（codepad.org已验证）

2.最长不连续公共子串（codepad.org已验证）

3.字符串的编辑距离(codepad.org已验证）

4.上下两个等长数组，可互换同下标元素，求上下两数组和可能的最小差值（codepad.org已验证）

5.连续子数组的最大和(codepad.org已验证）

 

代码都为简单实现版，均为递归算法，用作练手和思路记录。

 

1.最长递增子串

#define MAX 10000
#include
#include
int getMaxIncrease(int * input, int size){
    if(input == NULL) return 0;
    int maxLen = 1;
    int pre[MAX] = {0};
    int cur[MAX] = {0};
    //fill pre
    int i;
    pre[0] = input[0];
    for(i = 1; i<size; i ){
        pre[i] = input[i]<pre[i-1]? input[i] : pre[i-1];
    }
    //fill cur
    int startIndex = 1;
    for(;startIndex< size; startIndex ){
        for(i = 0; i<size; i ){
            if(i<startIndex){
                cur[i] = 0;
                continue;
            }

            if(cur[i-1] == 0 ){
                if(input[i]>pre[i-1] && pre[i-1]!=0)
                    cur[i] = input[i];
                else
                    cur[i] = 0;
            }
            else{
                cur[i] = cur[i-1];
                if(input[i]< cur[i] && input[i]>pre[i-1])
                    cur[i] = input[i];
            }
        }
        memcpy(pre,cur, sizeof(int)*MAX);
        cur[size-1]!=0? maxLen : 1;
    }
        return maxLen;
}
int main(){
    int input[] = {1,3,2,3,5,6};
    printf("maxLen = %d \n", getMaxIncrease(input,sizeof(input)/sizeof(int)));
}

2.最长不连续公共子串

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int LCS(const char* src, const char* dest, int sIndex, int dIndex){
        if(src == NULL || dest == NULL) return -1;
    if(sIndex <0 || dIndex<0)
        return 0;
    int equal, backsrc, backdest;
    equal = backsrc = backdest = 0;
    if( *(src sIndex) == *(dest dIndex)){
          equal = LCS(src, dest, sIndex-1, dIndex-1) 1;
    }
    backsrc = LCS(src, dest, sIndex-1, dIndex);
    backdest = LCS(src, dest, sIndex, dIndex-1);
    int max = equal;
    max = max>backsrc ? max : backsrc;
    max = max>backdest ? max : backdest;
    return max;
}
int main(){
    char* src = "aabbcc";
    char* dest = "abc";
    printf("%d", LCS(src, dest, strlen(src) -1 ,strlen(dest) -1));
}

3.字符串的距离

precondition: strlen(src)>= strlen(dest);

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


int getDis(const char* src, const char* dest){
        printf("src = %s dest = %s \n", src, dest);
    if(src == NULL || dest == NULL) return -1;
        if(!*dest || !*src){
        return strlen(src) + strlen(dest);
        }
    if(*src == *dest){
        src++;
        dest++;
        return getDis(src,dest);
    }
    if(*src== *(dest+1)){
                dest++;
                src++;
        return getDis(src,dest) + 1;
    }
        if(*(src+1)== *dest){
                src++;
        return getDis(src,dest) + 1;
    }

    src++;
        return getDis(src,dest)+1;
}
int main(){
    char* src = "aabbcc";
    char* dest = "abc";
    printf("%d \n", getDis(src, dest));
    printf("%d \n", getDis(src, "ec"));
    printf("%d \n", getDis(src, "ac"));
    printf("%d \n", getDis(src, "acce"));

}

4.交换元素求最小差值

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 10000

int getMin(int sum, int *up, int *down, int size){
    int min = sum;
    int record[MAX] = {sum};
    int i = 0;
    int count = 1;
    for(;i<size;i++){
        int tmpcount = count;
        int c = 0;
        for(;c<tmpcount ;c++){
                        count++;
            record[count] = record[c] - 2*(up[i]-down[i]);
            //printf("-----------%d\n", record[count]);
            int tsum = record[count];
            if(tsum<0) tsum*=-1;
            min = min>tsum?tsum:min;
                        if(min == 0) return min;
        }
    }
    return min;
}
int main(){
    int up[] = {1,4,5,3};
    int down[] = {3,2,2,0};
    int i = 0;
    int sum = 0;
    for(;i<sizeof(up)/sizeof(int);i++){
        sum+=(up[i]-down[i]);
    }
    printf("%d \n", getMin(sum,up,down, sizeof(up)/sizeof(int)));

}

5.连续子数组最大和

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#define MAX 10000
int getMaxSum(int *input, int size){
    if(input == NULL) return -1;
    int maxsum = -MAX;
    int pre[MAX] = {0};
    int cur[MAX] = {0};
    int i;
    for(i=0;i<size;i++)
        pre[i] = input[i];
    int end = 1;
    for(;end<size;end++){
        for(i = 0; i<size; i++){
            if(i<end) cur[i] = -1*MAX;
            else{
                cur[i] = input[i] + pre[i-1];
            }
            maxsum = maxsum>cur[i]?maxsum:cur[i];

        }
        memcpy(pre, cur, sizeof(int)*MAX);
    }
    return maxsum;
}

int main(){
    int input[] = {4,-3,10,4,-4,5};
    printf("%d \n", getMaxSum(input,sizeof(input)/sizeof(int)));
}