我一直在尝试解决这个TopCoder问题，我现在无法想出基于DP的解决方案（如下所示） . 我还找到了其他人解决问题的解决方案（下面也给出了），但我甚至无法理解 .
有人可以帮我解决这个问题吗？我不明白哪种思路会导致这个解决方案？我如何在脑海中 Build 复发关系？我完全不知道如何解决这个问题，或者编写该解决方案的人如何编写它 .
PS：我知道TopCoder有问题的社论，但是这个还没有发布 . 我不知道为什么 .
这是problem
Fox Ciel有很多功课要做 . 作业包括一些相互独立的任务 . 不同的任务可能需要不同的时间来完成 . 你得到一个int [] workCost . 对于每个i，第i个任务需要workCost [i]秒才能完成 . 她想参加一个派对并与她的朋友见面，因此她希望尽快完成所有任务 . 主要问题是包括Ciel在内的所有狐狸都非常讨厌做作业 . 每只狐狸都愿意做其中一项任务 . 幸运的是，哆啦A梦，一个来自22世纪的机器人猫，给了Fox Ciel一把分裂锤子：一个魔法小工具可以将任何狐狸分成两只狐狸 . 你得到一个int splitCost . 在狐狸上使用分裂锤是瞬间完成的 . 一旦在狐狸上使用锤子，狐狸开始分裂 . 在分秒成本后，她将变成两只狐狸 - 原始的狐狸和另一只全新的狐狸 . 当狐狸分裂时，不允许再次使用锤子 . 任务的工作不能中断：一旦狐狸开始处理任务，她必须完成它 . 多个狐狸不允许在同一任务上合作 . 当她使用锤子拆分时，狐狸无法完成任务 . 可以多次分割相同的狐狸 . 在解决其中一项任务之前和之后，可以分割狐狸 . 计算并返回狐狸可以解决所有任务的最短时间 .
这是solution：
1:
2: const int maxN = 55;
3: int dp[maxN][maxN*2];
4: int N;
5: int splitC;
6: vector<int> workC;
7:
8: int rec(int,int);
9: int FoxAndDoraemon::minTime(vector <int> workCost, int splitCost) {
10:
11: sort(workCost.begin(), workCost.end());
12: N = workCost.size();
13: splitC = splitCost;
14: workC = workCost;
15: memset(dp, -1, sizeof(dp));
16:
17: return rec(N-1, 1);
18: }
19:
20: int rec(int jobs, int fox)
21: {
22: if(jobs == -1) return 0;
23:
24: int& val = dp[jobs][fox];
25: if(val != -1) return val;
26: val = 0;
27:
28: if( (jobs+1) <= fox) val = max(workC[jobs] , rec(jobs-1, fox-1));
29: else
30: {
31: //split fox
32: val = splitC + rec(jobs, fox + 1);
33:
34: if( !(fox == 1 && jobs > 0) )
35: val = min(val, max(workC[jobs], rec(jobs-1, fox-1)));
36: }
37: return val;
38: }
39:
2 回答
DP问题通常需要您制定几个示例，而获得它的唯一方法就是练习 . 尝试解决DP中的一些标准问题类型，如最长增加子序列，背包，硬币更改，矩阵乘法，TSP等 . 尝试这些类型的变量 .
至于上述问题，很少有事情需要注意：
你需要N狐来完成N个任务（1个狐狸只能完成1个任务） . 所以，如果你需要再创建了.766116_t . 而且，如果你有超过1个任务，你必须拆分第一只狐狸 .
每只狐狸你可以做两件事
拆分它然后计算所花费的最短时间
不要拆分，而是执行当前任务并计算用少量狐狸执行剩余任务所需的时间 .
请注意，如果您有超过1个Fox（或1个Fox有1个任务），您只能选择不拆分 .
这应该可以让您了解问题 . 我没有彻底分析问题，但递归似乎没有创建重叠调用，即如果我有3个任务和2个狐狸，我只会调用该状态一次而不是更多 . 因此，解决方案是常规的递归解决方案，而不是DP .
社论现在在TopCoder网站上 . 你可以看看那里！