荣誉版主
- 积分
- -2403
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2010-5-4
- 最后登录
- 1970-1-1
|
找最短的那个值比较容易, 如果只找值得话一维矩阵就够了, 但是要打印路径就得用二维矩阵把每一步的DP都存下来然后倒过来推:
- const int N = 5;
- struct COORDINATE
- {
- int i;
- int j;
- COORDINATE(int x, int y) : i(x), j(y) {}
- };
- void PrintPath(int A[N][N])
- {
- int DP[N][N];
- DP[0][0] = A[0][0];
- for (int i = 1; i < N; i++)
- {
- DP[0][i] = DP[0][i-1] + A[0][i];
- }
- for (int i = 1; i < N; i++)
- {
- for (int j = 0; j < N; j++)
- {
- if (0 == j)
- DP[i][j] = DP[i-1][j] + A[i][j];
- else
- DP[i][j] = A[i][j] + max(DP[i][j-1], DP[i-1][j]);
- }
- }
- stack<COORDINATE> stk;
- int x = N-1;
- int y = N-1;
- while(x != 0 || y != 0)
- {
- stk.push(COORDINATE(x, y));
- if (0 == x)
- y--;
- else if (0 == y)
- x--;
- else
- {
- if (DP[x][y] == A[x][y] + DP[x-1][y])
- x--;
- else
- y--;
- }
- }
- stk.push(COORDINATE(0, 0));
- while (!stk.empty())
- {
- cout<<"("<<stk.top().i<<","<<stk.top().j<<")"<<endl;
- stk.pop();
- }
- }
复制代码 |
|