【DP】LeetCode - 120. Triangle、贝壳找房“采木头，锯子斧头”问题

锯子和斧头轮流砍树问题： 第一行输入树的个数 n, 接下来的 n 行，每行分别输入三个数 a、b、c，分别代表用锯子和斧头砍该棵树的时间，以及换工具砍树所需要的时间。现在手上是斧头，问看完这些树，最短需要多长时间。
输入：
3
20 40 20
10 4 25
90 100 5
输出：139

Explanation：第一棵树用斧头砍（40），第二颗树还用斧头（4），第三棵树，换成锯子（5 + 90）

  在牛客上看题，看到了一道用锯子斧头砍木头的问题，感觉应该很简单，但是同学说他提交只过了 9%，看了看代码感觉没有任何问题，最后再找到原因。首先这道题就是贪心，其实不是dp，叫dp也可以，就是

dp[0] = min(dp[0], dp[1] + b + c) + a;
dp[1] = min(dp[1], dp[0] + a + c) + b;

其中，dp[0] 是锯子，dp[1] 是斧头，a、b、c分别是当前次，锯子、斧头、切换工具的消耗。逻辑很简单，但是上边的代码有一个隐蔽的漏洞个，就是在算 dp[1] 的时候是用到 dp[0] 的值的，dp[0] 已经修改了，所以需要先存起来才行。代码如下：

#include 
#include 
using namespace std;
int main() {int n, a, b, c;cin >> n >> a >> b >> c;int dp[2] = { a + c, b };	// 0: 锯子, 1: 斧头for (int i = 1; i < n; ++i) {cin >> a >> b >> c;const int dp0 = dp[0];dp[0] = min(dp[0], dp[1] + c) + a;dp[1] = min(dp[1], dp0 + c) + b;}cout << min(dp[0], dp[1]) << endl;
}

  这就是为什么很多人只过了 9%。
  这道题和 120. Triangle 是一样的，都可以从上到下dp，也可以从下到上dp。

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3, 4],
[6, 5, 7],
[4, 1, 8, 3] ]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

  题目里也写了用 O(N) 的空间，也就是和上边的思路意义一样，其实每一层只需要上一层的（从上到下），或者只需要下一层的（从下到上），只有一个一维数组就行，不需要全存起来。代码如下：

// top-down 
int minimumTotal1(vector<vector<int>>& triangle) {vector<int> res(triangle.size(), triangle[0][0]);for (unsigned int i = 1; i < triangle.size(); i++) for (int j = i; j >= 0; j--) {if (j == 0)res[0] += triangle[i][0];else if (j == i)res[j] = triangle[i][j] + res[j - 1];else res[j] = triangle[i][j] + min(res[j - 1], res[j]);}return *min_element(res.begin(), res.end());
}// bottom-up
int minimumTotal(vector<vector<int>>& triangle) {vector<int> res = triangle.back();for (int i = triangle.size() - 2; i >= 0; i--) for (unsigned int j = 0; j <= i; j++) res[j] = triangle[i][j] + min(res[j], res[j + 1]);return res[0];
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！