首页 > 代码库 > 动态规划总结与思考
动态规划总结与思考
动态规划 & 思索
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
那么如何使用刚才说过的三步思考方式去思考这个问题呢？
- 要解决以A为根的总问题，我们显然需要要知道各个子结点的收益值，而子结点的收益值有依赖于父节点A是否参加聚会，所以我们要进行分情况讨论，但是我们可以总结如下，所有的根节点的最大收益情况都可以总结为该节点参加或者不参加的情况下的收益情况，而且一个父节点的收益情况也只依赖儿子节点的这两种收益情况。于是我们分析得到，根节点的收益情况的计算是依赖子问题的收益情况的，如果我们直接使用递归的方法，但是我们会发现子问题的总个数是有限的，因为总共的节点个数是有限的，那么分别以每一个节点为计算单元就可以得到答案，但是这些单元之间的计算顺序是非常重要的，我们希望每个节点只被的收益值只被计算一次，那么这时候自底向上的思考方式就派上用场了，在计算A的时候我们需要知道B，C，D的收益信息值，这些信息包括B参与和不参与的收益信息，对于C和D也是同样的，要知道B的收益信息就需要知道它的儿子节点E和F的收益信息，经过上面的分析我们显然就很清楚了，如果我们能够从最后一层一层一层的向上计算收益，那么这时候的每个节点的收益值的计算就变得非常简单了。然后我想说对于树结构，可以使用后序遍历的方式来实现类似从最后一层网上走的过程，因为后序遍历的过程中所有的子结点的计算都是已经完成了的。
- 上面的问题我们可以看到，子问题，子问题的最优性（包括该节点是否参与的信息），子问题的有限性，自顶向上和自底向上的种种都出现了。
整齐打印问题的思考
考虑在一个打印机上整齐地打印一段文章的问题。输入的正文是n个长度分别为L1、L2、……、Ln（以字符个数度量）的单词构成的序列。我们希望将这个段落在一些行上整齐地打印出来，每行至多M个字符。“整齐度”的标准如下：如果某一行包含从i到j的单词（i<j），且单词之间只留一个空格，则在行末多余的空格字符个数为 M - (j-i) - (Li+ …… + Lj)，它必须是非负值才能让该行容纳这些单词。我们希望所有行（除最后一行）的行末多余空格字符个数的立方和最小。请给出一个动态规划的算法，来在打印机整齐地打印一段又n个单词的文章。分析所给算法的执行时间和空间需求。
要求所有行的额外的空格的平方和最小。
这个问题咋一看很像是一个贪心问题，而贪心的策略就是让每一行尽可能的多放单词，但是我们会发现这样的处理并不能得到全局的最优解。看来我们得改变思路了。
我们现在累分析W[1,n]的计算，为了计算从开始到最终的最优解，显然我们会有可能性。例如将wn当作最后一行，那么这时候前W[1,n-1]的就必须是最优的策略，为什么必须是最有的打印策略，这个可以使用反证法，当然，出了将wn当做最后一行外，我们还可以将wn-1,Wn 当作最后一样，那么前面的子问题就是W[1,n-2]，如此分析下去，我们自然是会有多种选择方式，假设最后K个词是满足同一行的最多的单词个数，那么就会有k中选择，这时候我们就只需要选中其中其中平方和最小的就可以了，现在终于得到解答了。那么前面的W[1,n-1]….W[1,n-k+1]又怎么计算呢，其实思路是一致的。
现在问题的描述已经非常的清楚了，但是我们还要分析一下，如何安排各个子问题的计算循序，我们会发现以从开始到第j个单词的最优最小平方和的计算只依赖于从开始到第将j-1，j-2,j-3 等一些列子问题，所以我们只需从左到右依次计算就可以了，就可以满足依赖了。
那么如何使用刚才说过的三步思考方式去思考这个问题呢？
显然刚才的问题我们已经进行了描述这个很有特点的问题，里面有很多的子问题，子问题的求解顺序也得到了描述，如果直接使用递归算法不保存子问题的答案，问题将是一个指数级别的问题，但是通过保存子问题的答案，我们可以将问题转换为O(N2)的算法。这里面同样是是使用了自顶向下的分析方法，而实现的时候我们使用自底向上的策略，子问题之间互相依赖。这样我们很自然的就使用动态规划的方法实现了。
//
// NeatyPrint.h
// HelloWorld
//
// Created by jackqiu on 14-12-31.
// Copyright (c) 2014年 jackqiu. All rights reserved.
//
#ifndef HelloWorld_NeatyPrint_h
#define HelloWorld_NeatyPrint_h
class NeatyPrint{
public:
int print(vector<int> words,int M)
{
int len = words.size();
int *dp = new int[len+1];
dp[0] = 0;
for(int i = 1;i<=len;i++)
{
int left = M - words[i-1];
int add = 0;
if(i!=len)
add = left*left*left;
dp[i] = add+dp[i-1];
for(int j=i-1;j>=1;j--)
{
left = left - 1 - words[j-1];
add = left*left*left;
if(left<0)
break;
if(i==len)
{
add = 0;
}
if(dp[j-1]+add<dp[i])
dp[i] = dp[j-1]+add;
}
}
int ret = dp[len];
for(int i=0;i<=len;i++)
cout<<dp[i]<<endl;
delete[] dp;
return ret;
}
};
#endif
动态规划总结与思考