c语言求解Redraiment走法

1.题目描述

   Redraiment是走梅花桩的高手。Redraiment可以选择任意一个起点，从前到后，但只能从低处往高处的桩子走。他希望走的步数最多，你能替Redraiment研究他最多走的步数吗？

2.求解思路

动态规划思路：

记d[i]为以任意一个A[i]为末尾元素组成的最长递增子序列的长度，找出所有位于i之前且比A[i]小的元素A[j]，此时可

出现两种情况：

（1）若找到，例如i = 2，此时A[i] = 7，比A[i]小的元素为A[0] = 4，A[1] = 5，取所有比A[i]小的元素中A[j]中，对应的d[j]最

大的加1，即d[i] = max{ d[j] }，其中j < i 且 A[j] < A[i]；

（2）若没有找到，例如i = 3，此时A[i] = 1，i之前不存在比1小的元素，此时A[3] = 1独自构成一个递增子序列，d[i] = 1。

3.源码实现

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

void lis(int *a, int n, int *b, int *m)
{
    int **c = (int **)malloc(n*sizeof(int *));
    int *d = (int *)malloc(n*sizeof(int));
    int *e = (int *)malloc(n*sizeof(int));
    int i, j, k;

    for(i=0; i<n; i++)
    {
        c[i] = (int *)malloc((i+1)*sizeof(int));
        /*c[i] = (int *)malloc((n)*sizeof(int));*/
    }

    d[0] = 1;
    e[0] = 1;
    c[0][0] = a[0];

    for(i=1; i<n; i++)
    {
        d[i] = 1;
        k = i;

        for(j=0; j<i; j++)
        {
            if(a[j] < a[i] && d[i] < d[j] + 1)
            {
                d[i] = d[j] + 1;
                k = j;
            }
        }

        if(k == i)
        {
            c[i][0] = a[i];
        }
        else
        {
            for(j=0; j<d[k]; j++)
            {
                c[i][j] = c[k][j];
            }

            c[i][j] = a[i];
        }

        e[i] = d[i];
        k = i;

        for(j=0; j<i; j++)
        {
            if(d[j] > e[i])
            {
                e[i] = d[j];
                k = j;
            }
        }

        for(j=0; j<d[k]; j++)
        {
            b[j] = c[k][j];
        }

        *m = d[k];
    }

    for(i=0; i<n; i++)
    {
        free(c[i]);
        c[i] = NULL;
    }

    free(c);
    free(d);
    free(e);

    c = NULL;
    d = NULL;
    e = NULL;
}

int main()
{
    int n = -1;
    int m = -1;
    int a[1024];
    int b[1024];
    int c[10];
    int i;

    memset(c, 0x00, sizeof(c));

    while(gets(c) != NULL)
    {
        n = atoi(c);

        if(n <= 0)
        {
            continue;
        }

        /*printf("n=%d\n", n);*/

        for(i=0; i<n; i++)
        {
            scanf("%d", a+i);
        }

        /*for(i=0; i<n; i++)
        {
            printf("%d\n", a[i]);
        }*/

        memset(b, 0x00, sizeof(b));

        lis(a, n, b, &m);

        printf("%d\n", m);

        /*for(i=0; i<m; i++)
        {
            printf("%d\n", b[i]);
        }*/

        memset(c, 0x00, sizeof(c));
    }

    return 0;
}