📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 2152| 回复: 3
跳转到指定楼层
上一主题 下一主题
收起左侧

Microsoft: 打印最优路径

🔗
wwwyhx | 只看该作者 |倒序浏览
全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
一个NxN矩阵,每个格子有一个整型数,从左上角到右下角找一条路径使得经过的格
子数字和最大。只能向右和下移动。时间复杂度,如何优化

上一篇:Google : Calculate volume
下一篇:Microsoft : Judge binary tree equality with swapping allowed
🔗
ziegfeld 2011-10-28 05:28:30 | 只看该作者
全局:
动态规划
到最后一行/一列要处理一下
回复

使用道具 举报

🔗
sprime 2011-10-28 22:20:01 | 只看该作者
全局:
时间复杂度m*n,扫一次就行
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-10-30 04:29:59 | 只看该作者
全局:
找最短的那个值比较容易, 如果只找值得话一维矩阵就够了, 但是要打印路径就得用二维矩阵把每一步的DP都存下来然后倒过来推:

  1. const int N = 5;

  2. struct COORDINATE
  3. {
  4.         int i;
  5.         int j;

  6.         COORDINATE(int x, int y) : i(x), j(y) {}
  7. };

  8. void PrintPath(int A[N][N])
  9. {
  10.         int DP[N][N];
  11.         DP[0][0] = A[0][0];
  12.         for (int i = 1; i < N; i++)
  13.         {
  14.                 DP[0][i] = DP[0][i-1] + A[0][i];
  15.         }

  16.         for (int i = 1; i < N; i++)
  17.         {
  18.                 for (int j = 0; j < N; j++)
  19.                 {
  20.                         if (0 == j)
  21.                                 DP[i][j] = DP[i-1][j] + A[i][j];
  22.                         else
  23.                                 DP[i][j] = A[i][j] + max(DP[i][j-1], DP[i-1][j]);
  24.                 }
  25.         }

  26.         stack<COORDINATE> stk;
  27.         int x = N-1;
  28.         int y = N-1;
  29.         while(x != 0 || y != 0)
  30.         {
  31.                 stk.push(COORDINATE(x, y));
  32.                 if (0 == x)
  33.                         y--;
  34.                 else if (0 == y)
  35.                         x--;
  36.                 else
  37.                 {
  38.                         if (DP[x][y] == A[x][y] + DP[x-1][y])
  39.                                 x--;
  40.                         else
  41.                                 y--;
  42.                 }
  43.         }

  44.         stk.push(COORDINATE(0, 0));

  45.         while (!stk.empty())
  46.         {
  47.                 cout<<"("<<stk.top().i<<","<<stk.top().j<<")"<<endl;
  48.                 stk.pop();
  49.         }
  50. }
复制代码
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表