算法(四)-数学三角问题

题目描述：

给定一个有n行数字组成的数学三角形。设计一个算法，计算从三角形顶至底的一条路径，使该路径经过的数字的总和最大。

7

3     8

8     1      0

2      7     4      4

4     5      2       6      5

这个题目是使用到了动态规划，而且是典型的动态规划

解析：

从底向上找，比如

找4+2大，还是5+2大

再找5+7大，还是2+7大，

。。。。。。

以此类推，找出底部加上倒数第二行的数，值最大的。这样也就确定了最后一行应该选取哪个数。

以此类推，找出倒数第二行，倒数第三行，直到最顶行。

代码：
注：是在linux上面，用Qt写的，但是不知道为什么那次Qt突然不能使用中文了，所以就用英文添加了注释

//arthor = "lee"
//page = 80 question = 3-4
//time = 2015.11.3
#include <iostream>
using namespace std;

int main()
{
    int **mathTriangle;//mathTriangle
    int **valueTriangle;//valueTriangle
    int count;//the hight of mathTriangle and valueTriangle
    cin>>count;
    count = count + 1;

    /*get the memery*/
    mathTriangle = new int*[count];
    valueTriangle = new int*[count];
    for(int i = 0; i < count; i++)
    {
        mathTriangle[i] = new int[count];
        valueTriangle[i] = new int[count];
    }

    /*init the data*/
    for(int i = 0; i < count; i++)
        for(int j = 0; j < count; j++)
        {
            mathTriangle[i][j] = 0;
            valueTriangle[i][j] = 0;
        }

    /*get the data of user input*/
    for(int i = 1, tempCount = 1; i < count; i++)
    {
        for(int j = 1; j <= tempCount; j++)
            cin >> mathTriangle[i][j];
        tempCount++;
    }

    /*create the table*/
    for(int i = 1; i < count; i++)//init the lowest number
        valueTriangle[count-1][i] = mathTriangle[count-1][i];
    for(int i = count - 1, tempCount = count - 2, temp1, temp2; i > 1; i--)
    {
        for(int j = 1; j <= tempCount; j++)
        {
            temp1 = valueTriangle[i][j] + mathTriangle[i-1][j];
            temp2 = valueTriangle[i][j+1] + mathTriangle[i-1][j];
            temp1 > temp2 ? valueTriangle[i-1][j] = temp1 : valueTriangle[i-1][j] = temp2;
        }
        tempCount--;
    }
    cout<<"the count of the best rout is : "<<valueTriangle[1][1]<<endl;
//    /*test for output*/
//    for(int i = 1; i < count; i++)
//    {
//        for(int j = 1; j < count; j++)
//            cout<<valueTriangle[i][j]<<" ";
//        cout<<endl;
//    }

    return 0;
}