动态规划/深度、广度图搜索

Question

一段道路，被分成一块一块的，并且被顺序的编号为1,2,3,4,5...，道路常年使用出现了损坏， 比如，编号为5, 8， 19， 21. 四段出现损坏。修复的方式是指定长度的段替换，比如指定采用3个块长度来替换，修复编号为5的块时，可以替换3,4,5这一组，也可以4,5,6，或者5,6,7这一组，同理，修复编号为8的块时也一样，如果同时考虑编号为5和8的块时，可以重叠，比如，对编号为5修复{5,6,7}，对编号为8修复{6,7.8}， 那么修复的总长度是 4， 小于原先单独修复编号5和8的长度（3+3）。案例编号为5, 8， 19， 21. 四段出现损坏，修复的最短长度是7，修复的{5,6,7,8}（其中6.7是重复的）和{19,20,21}。 当指定修复长度可变，坏点个数可变，坏点位置可变，求最短修复长度？

Answer 1

https://blog.csdn.net/linraise/article/details/9957057