返回信息流leetcode----337. House Robber III
实在难以理解,动态规划的解法...
动态转移方程可以理解 就是代码理解不了...
跪求 如何学习动态规划问题???
真的向放弃这块了
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #90818同步于 2016/8/17
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
[leetcode]动态规划的问题跪了=.=求大神指导如何学习动态规划??
Mohn
2016/8/17镜像同步38 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
这特么明明就是记忆化的DFS嘛。。。
装什么象啊。。。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
const int INF = 0x3f3f3f3f;
class Solution {
public:
int rob(TreeNode* root) {
return do_rob(root, false);
}
private:
int do_rob(TreeNode* root, bool pre) {
if (root == NULL) {
return 0;
}
if (pre && tmp.find(root) != tmp.end()) {
return tmp[root];
}
if (!pre && fmp.find(root) != tmp.end()) {
return fmp[root];
}
int res = -INF;
if (!pre) {
res = max(res, root->val + do_rob(root->left, true) + do_rob(root->right, true));
}
res = max(res, do_rob(root->left, false) + do_rob(root->right, false));
if (pre) {
tmp[root] = res;
}
if (!pre) {
fmp[root] = res;
}
return res;
}
private:
unordered_map<TreeNode*, int> tmp, fmp;
};
可以哒
【 在 Mohn (【意涵团】offer快到碗里来) 的大作中提到: 】
: leetcode----337. House Robber III
: ...................
300道！
【 在 whn6325689 (Mr. Phoebe) 的大作中提到: 】
: 哇！我从大一开始起码做了300道各种类型的DP，然而还是不会。
: 所以就果断交给队友处理。
: 有时候这是一种天赋问题，你要试过才知道。