动态规划

1子序列的最大和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

int maxSubArray(int* nums, int numsSize){
    int max = nums[0];
    int sum = nums[0];
    int tmp;
    for(int i=1; i< numsSize; i++){
        sum = nums[i] + (sum > 0 ? sum : 0);
        max = sum > max ? sum : max;
    }
    return max;
}

2、最长递增子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。

int lengthOfLIS_01(int* nums, int numsSize) {
    if (numsSize < 2) {
        return numsSize;
    }
    int lis[numsSize];

    int i, j, result = 0;
    for (i = 0; i < numsSize; i++) {
        lis[i] = 1;
        for (j = 0; j < i; j++) {
            if (nums[i] > nums[j] && lis[j] + 1 > lis[i]) {
                lis[i] = lis[j] + 1;
            }
        }
        result = result > lis[i] ? result : lis[i];
    }
    return result;
}

3、最长公共子序列

int LCS(char x[],char y[])
{
    int i,j;
    int x_len,y_len;
    x_len = strlen(x);
    y_len = strlen(y);

    for(i = 1;i <= x_len;i++)
    {
        for(j = 1;j <= y_len;j++)
        {
            if(x[i-1] == y[j-1])
            {
                c[i][j] = c[i-1][j-1] +1;
                b[i][j] = 0;
            }
            else
            {
                c[i][j] = Max(c[i-1][j],c[i][j-1],i,j);
            }
        }
    }
        return c[x_len][y_len];
}

4、最小编辑距离

int cmp_levenshtein( const char *s1, const char *s2 )
{
    int row = strlen(s1);               /* s1 的长度 */
    int col = strlen(s2);               /* s2 的长度 */

    int mat[row][col];                  /* C99 - variable-length array */

    for( int i=0; i<row; ++i ) {        /* 数组的行 */
        for( int j=0; j<col; ++j ) {    /* 数组的列 */
            if( i == 0 ) {
                mat[i][j] = j;          /* 初始化第1行为 [ 0 1 2 ... ] */
            }
            else if( j == 0 ) {
                mat[i][j] = i;          /* 初始化第1列为 [ 0 1 2 ... ] */
            }
            else {
                int cost = ( s1[i-1] == s2[j-1] ) ? 0 : 1;     /* 记录s1[i-1]与s2[j-1]是否相等 */
                mat[i][j] = MIN3( mat[i-1][j  ] + 1,           /* 取三者的最小值 */
                                  mat[i  ][j-1] + 1,
                                  mat[i-1][j-1] + cost);
            }
        }
    }

    return mat[row-1][col-1];
}