动态规划 & 思索
1 首先要先分析问题的结构，也记得自顶向下的去考虑一个问题，使用自顶向下的想法是在尝试着使用递归的方法，递归的过程中就会出现子问题，然后我们在去分析如果直接使用分治的方法的时间复杂性是多少，如果是指数级别的，那么我们就要进行第二步的思索。
2 这些自问题是否是独立的，如果不是独立的，那么自问题的个数是否是有多项式级别的，如果这个问题的子问题之间有交叉，而且子问题的个数是有限的，那么请进入第三步的思考方式？
3 子问题之间是否可以互相依赖，比如最优性的依赖，如果一个问题是的解是最有的，那么它的子问题的答案也应该是最优的，这个往往可以使用剪切粘贴的策略给予证明，也就是假设问题的子问题不是最优的，那么这时候就可以使用一个更好的解答来代替原来的子问题的解答，这样就可以得到一个更好的答案了，于是找到了矛盾。
如果一个问题满足上面的三个条件，我向这个问题基本上就是可以使用动态规划方法来解决了。
公司聚会问题
今天看了一个公司聚会计划的题目，觉得很有意思？
Stewart教授是一家公司总裁的顾问，这家公司计划一个公司聚会。这个公司有一个层次式的结构；也就是说，管理关系形成一棵以总裁为根的树。人事部给每个雇员以喜欢聚会的程度来排名，这是个实数。为了使每个参加者都喜欢这个聚会，总裁不希望一个雇员和他（她）的直接上司同时参加。
Stewart教授面对一棵描述公司结构的树，使用了左子女、右兄弟表示法。树中每个结点除了包含指针，还包含雇员的名字和该雇员喜欢聚会的排名。描述一个算法，它生成一张客人列表，使得客人喜欢聚会的程度的总和最大。分析你的算法的执行时间。
如何才能求出以A为根的最大收益，显然这时候根据题目的要求，如果A参加了聚会，那么B,C,D就不可以参加聚会了，如果A不参加聚会，那么B，C，D都有机会参加聚会，但是并不是说A不参加聚会，B，C，D就一定要参加聚会。经过上面的递推公式，我们还不能很好的编写动态规划的程序，现在我们来分析一下，其实我们会发现这个处理过程有点类似树的后序遍历，也就是要先访问完所有的儿子节点再来访问图本身这个节点。但是如果直接使用深度优先搜索的方法的话是不是也就可以了，当所有的儿子节点都访问我之后，就直接可以访问父节点了。当然为了使得能够直接获取儿子节点的信息，我们希望能够直接保存已经处理过的根节点。
其中
//
// Meeting.h
// HelloWorld
//
// Created by jackqiu on 14-12-31.
// Copyright (c) 2014年 jackqiu. All rights reserved.
//
#ifndef HelloWorld_Meeting_h
#define HelloWorld_Meeting_h
#include "TreeNode.h"
struct MeetNode
{
MeetNode* child,*subling;//左儿子，有兄弟的表示方法
int key,_key;//参与时的最大收益值
int val;//该节点的收益值
MeetNode(int k1,int k2):key(k1),_key(k2)
{
child = NULL;
subling = NULL;
}
MeetNode(int _val):val(_val)
{
key =0;
_key = 0;
child = nullptr;
subling = nullptr;
}
};
class Meeting
{
//#define MAX_NODE 100
public:
int maxProfile(MeetNode* root)
{
maxMeetingProfile(root);
if(root==nullptr)
return 0;
int max = root->key>root->_key?root->key:root->_key;
return max;
}
private:
void maxMeetingProfile(MeetNode *root)
{
if(root->child)
{//如果存在儿子节点就先将所有的儿子节点的收益值都先求出来
MeetNode* firstChild = root->child;
maxMeetingProfile(firstChild);
while(firstChild->subling)
{
maxMeetingProfile(firstChild->subling);
firstChild = firstChild->subling;
}
}
else//如果节点是叶子节点那么，该节点参与其中的收益就是val，而不参与其中的收益就为0
{
root->key = root->val;
root->_key = 0;
return;
}
//root 参与
MeetNode* firstChild = root->child;
int sum = firstChild->_key+root->val;
while(firstChild->subling)
{
sum+=firstChild->subling->_key;
firstChild = firstChild->subling;
}
//root 不参与的时候的最大收益值
firstChild = root->child;
sum = 0;
int max = firstChild->key>firstChild->_key?firstChild->key:firstChild->_key;
sum+=max;
while(firstChild->subling)
{
max = firstChild->subling->key>firstChild->subling->_key?firstChild->subling->key:firstChild->subling->_key;
sum+=max;
firstChild = firstChild->subling;
}
}
};
#endif
那么如何使用刚才说过的三步思考方式去思考这个问题呢？
整齐打印问题的思考