一段时间以来，我一直在尝试解决这个 TopCoder 问题，但我无法提出基于 DP 的解决方案来解决这个问题（如下所示）。我还找到了其他人对该问题的解决方案（也在下面给出），但我什至无法理解。
谁能帮我解决这里的问题？我不明白什么思路会导致这个解决方案？如何在我的脑海中建立递归关系？我完全不知道如何解决这个问题，或者编写该解决方案的人是如何编写它的。
PS：我知道TopCoder 有问题的社论，但是这个还没有发布。我不知道为什么。
这就是问题所在
Fox Ciel 有很多功课要做。作业由一些相互独立的任务组成。不同的任务可能需要不同的时间来完成。您将获得一个 int[] workCost。对于每个 i，第 i 个任务需要 workCost[i] 秒才能完成。她想参加一个聚会和认识她的朋友，因此她想尽快完成所有任务。
主要的问题是，包括夏尔在内的所有狐狸都非常讨厌做作业。每只狐狸只愿意做其中一项任务。幸运的是，来自 22 世纪的机器猫哆啦A梦给了 Fox Ciel 一把分裂锤：一个可以将任何狐狸分成两只狐狸的魔法小工具。
你得到一个 int splitCost。在狐狸身上使用劈锤是瞬间的。一旦在狐狸身上使用锤子，狐狸就会开始分裂。splitCost 秒后，她会变成两只狐狸——原来的狐狸和另一只全新的狐狸。狐狸在劈叉时，不能再用锤子打她。
一项任务的工作不能被打断：一旦狐狸开始执行一项任务，她就必须完成它。不允许多只狐狸在同一任务上合作。狐狸在使用锤子被劈开时无法完成任务。可以多次拆分同一只狐狸。在狐狸完成其中一项任务之前和之后都可以分裂狐狸。
计算并返回狐狸可以解决所有任务的最短时间。
这是解决方案：
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: