我在为这个DP问题设计解决方案时遇到了问题
假设您想要从A市旅行到B市。在途中有n个中途停留地点，您可以选择多个酒店选择停留在每个中途停留地点。所涉及的费用是一些酒店在中途停留时的旅行费用（让我们称之为tij，我是当前的中途停留，j是下一个）以及在中途停留的酒店停留的费用（让我们称之为sj）。设计动态编程算法以选择城市B中的最佳路线和酒店，从而最大限度地降低整个行程的成本。分析其正确性和运行时间。
这是一个可能正确的算法：将止损定义为a1，a2，a3，a4，a5，a6 ..... an，每个止损的最小成本为c1，c2，c3，c4，c5 ...... cn
第一站。计算从城市A到a1的路线成本并将其存储在c1中。
第二站。计算从A到a2的路由成本，并计算从a1到a2加c1的路由成本。选择较小的成本并将其存储到c2
第三站。计算从A到a3的路由成本，a1到a3加c1的成本，以及a2到a3加c2的成本。选择最小的成本并将其存储到c3
.... ... .
最后，我们可以找到cn + 1，这是从A到B的最小成本，步骤与上述相同
动态表达式为ci = min（c1 + t（1，i），c2 + t（2，i），c3 + t（3，i），....，c（i-1）+ t（i -1，i））的
我们尝试所有可能的路线到每个站点并找到最小的成本，因此我们选择的路线答案是最小化的
这种算法的运行时间为O（n ^ 2），考虑建立一个大小为n * n的二维数组