【USACO】numtri

给一颗数字树，让找一条数字和最大的路径。一下子就想起刚学不久的回溯法了。照着写了个代码，调了调搞通了。在小数据的情况下是对的，但是在test 6 树有199层的时候溢出了。

#include <stdio.h>
int BackTrack(int n, int (*num)[1000], int * summax) //回溯法
{
    *summax = 0;
    int sum = 0;
    int k = 0;
    int S[1000] = {0};
    int sign[1000] = {0};
    int sumn[1000] = {0};  //保存算到第k行的和
    S[k] = 1;
    sign[k] = 0;
    do{
        while(S[k] != 0)
        {
            if(S[k] == 1 && k != 0)
            {
                sign[k]++; //选择右边的数
            }
            if(k == 0)
            {
                sumn[k] = num[k][sign[k]];
            }
            else
            {
                sumn[k] = sumn[k - 1] + num[k][sign[k]];
            }
            S[k]--;
            if(k < n - 1)
            {
                k++;
                S[k] = 2; //新到一行时 共有两个选择
                sign[k] = sign[k - 1] + 2 - S[k];  //选择左边的数
            }
            else
            {
                if(sumn[k] > *summax)
                {
                    *summax = sumn[k];
                }

            }
        }
        k--;
    }while(k > 0);
    return 0;
}

int main()
{
    FILE *in, *out;
    in = fopen("numtri.in", "r");
    out = fopen("numtri.out", "w");

    int N;
    int num[1000][1000];
    int summax;
    int i, j;
    fscanf(in, "%d", &N);
    for(i = 0; i < N; i++)
    {
        for(j = 0; j <= i; j++)
        {
            fscanf(in, "%d", &num[i][j]);
        }
    }

    BackTrack(N, num, &summax);
    fprintf(out, "%d
", summax);

    return 0;
}

-------------------------------------------------------------

针对回溯法溢出，很容易想到的是计算有冗余。举例来说：在计算5的分支时，其实下面7的情况已经在之前都算过了的，只要知道7 和 8哪个数对应的下面的和最大就好了。

4 5

6 7 8

9 10 11 12

于是可以换成从下到上的解法，从最底下开始计算在每一层对应位置上和最大的数，最下面一层就是数本身，再往上每次都是数本身 + max(下一行左边最大求和数，下一行右边最大求和数)，在最高层时输出最大值。写完代码后很奇怪，自己的电脑上跑总是溢出，但在测评系统上却AC了。

#include <stdio.h>

int max(int a, int b)
{
    return a > b ? a : b;
}

int tmp[1000] = {0}; //每层用同一个tmp存储最大值就好了，因为在计算出高层的最大值后，低层的最大值就没有用了。
int downtotop(int c, int N, int (*num)[1000])
{
    int i;
    if(c == N)
    {
        if(c != 1)
        {
            for(i = 0; i < c; i++)
            {
                tmp[i] = num[c - 1][i];
            }
            downtotop(c-1, N, num);
        }
        else //针对只有一个数的情况
        {
            return num[0][0];
        }
    }
    else
    {
        for(i = 0; i < c; i++)
        {
            tmp[i] = num[c - 1][i] + max(tmp[i], tmp[i + 1]);
        }
        if(c == 1)
        {
            return tmp[0];
        }
        else
        {
            downtotop(c-1, N, num);
        }
    }
}

int main()
{
    FILE *in, *out;
    in = fopen("numtri.in", "r");
    out = fopen("numtri.out", "w");

    int N;
    int num[1000][1000];
    int summax;
    int i, j;
    fscanf(in, "%d", &N);
    for(i = 0; i < N; i++)
    {
        for(j = 0; j <= i; j++)
        {
            fscanf(in, "%d", &num[i][j]);
        }
    }

    summax = downtotop(N, N, num);
    fprintf(out, "%d
", summax);

    return 0;
}

-------------------------------------------

经过好友点拨，发现是int num[1000][1000]太大了，超过了栈内存，必须动态分配。改好后自己在电脑上也跑通了。在测评系统上消耗的内存也小了。

    int i;
    int N;
    fscanf(in, "%d", &N);

    int **num = (int **)malloc(1000 * sizeof(int *));
    for(i = 0; i < N; i++)
    {
        num[i] = (int *)malloc(1000 * sizeof(int));
    }

--------------------------------------

看了答案还是想复杂了不需要递归的直接for循环就好

　for (i = 0; i < rows; i++)
    res[i] = tri[rows-1][i];

  for (i = rows-1; i > 0; i--)
    for (j = 0; j <= i; j++)
      res[j] = tri[i-1][j] + max(res[j],res[j+1]);

-----------------------------------

答案还有一种从上到下的思路，不用先把数字存下来，可以取一个计算一步。如同从上到下，每次有两个选择，从下到上每次也是两个选择（边上的只有一个选择），从上往下加时可以只选择两个上方已有数字钟最大的，最后可以得到最下方N个最大值，选出其中最大的一个即可。

    for(i=1; i<=r; i++) {
        memmove(oldbest, best, sizeof oldbest);
        for(j=0; j<i; j++) {
            fscanf(fin, "%d", &n);
            if(j == 0)
                best[j] = oldbest[j] + n;
            else
                best[j] = max(oldbest[j], oldbest[j-1]) + n;
        }
    }