面试题47：礼物的最大值

题目如书上
动态规划问题。

/*
思路：跟迷宫类似，按照给定方向遍历，给出最后的最大值。
1.建立方向数组
2.建立礼物最大值矩阵，与原始输入矩阵维度一样，每个点存储着从起点到该点得到的礼物的最大值。
*/
int presentValue(vector<vector<int> >&present, int m, int n)
{
    if (present.size() <= 0 || m <= 0 || n <= 0)
        return 0;
    vector<vector<int> >mostValue(m, vector<int>(n, 0));
    //定义可移动方向
    int dx[] = { 0,1 };
    int dy[] = { 1,0 };
    mostValue[0][0] = present[0][0];
    for (int i = 0; i < m; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            for (int d = 0; d < 2; ++d)
            {
                int x = i + dx[d], y = j + dy[d];
                //从[i,j]点向下或向右移动
                if (x >= 0 && x < m && y >= 0 && y < n)
                {
                    mostValue[x][y] = max(mostValue[x][y], mostValue[i][j] + present[x][y]);
                }

            }
        }
    }
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << mostValue[i][j] << "  ";
        }
        cout << endl;
    }
    return mostValue[m - 1][n - 1];
}

int main()
{
    //vector<vector<int> > present = { {1,10,3,8},{12,2,9,6}, {5,7,4,11},{3,7,16,5} };
    vector<vector<int> > present = { {10}};
    int m = present.size(), n = present[0].size();
    cout << presentValue(present, m, n) << endl;
    return 0;
}