挑战程序设计竞赛p47页,对于释放囚犯问题泛化为如果某一个问题的解,依赖于子问题的解,且没有重叠,那么就可以从底至上的迭代解决,通保存子问题的解来求得最钟问题的解。
这里我们看到对于当前释放的囚犯,那么知道当前最优解等于释放左边当中全部囚犯最优解+释放右边当中全部囚犯最优解+当前解(=A[j]-A[i]-2,考虑A[j],A[i]是两个端点)
这里我们注意初始化二维矩阵,最终可以求得一个上三角矩阵。