动态规划:数字三角形

void main()
{
    ifstream input("input.txt");
    ofstream output("output.txt");

    int n;
    int s[101][101] = { 0 };
    input >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            input >> s[i][j];
        }
    }
    int max[101][101] = { 0 };
    for (int i = 1; i <= n; i++)
    {
              max[n][i] = s[n][i];
    }
    for (int i = n - 1; i >= 1; i--)
    {
        for (int j = 1; j <= i; j++)
        {//计算第 i 层的每一个点的 max[][]
            int one = max[i + 1][j];
            int two = max[i + 1][j + 1];
            if (one > two)
            {
                max[i][j] = s[i][j] + one;
            }
            else
            {
                max[i][j] = s[i][j] + two;
            }
        }
    }
    output << max[1][1];
    input.close();
    output.close();
}

0

Leave a Reply

Your email address will not be published.