Python动态规划实现商铺选址最优成本时dp[i][j]填充疑问

空缺处的正确写法为：

min(dp[i][j], dp[i-1][r] + cost[r+1][j])

逻辑说明 #

你定义的dp[i][j]是前j个城市中心修建i个商铺的最低成本，最内层循环的r为拆分点，逻辑如下：

• 前r个城市中心修建i-1个商铺，对应的最低成本为dp[i-1][r]
• 剩余的第r+1到第j个城市中心修建1个商铺，对应的成本为你提前预处理完成的cost[r+1][j]
• 遍历所有合法的拆分点r，取所有拆分方案中总成本的最小值，即可得到dp[i][j]的取值

代入你给出的测试用例k=5, A = [1, 2, 3, 6, 7, 9, 11, 21, 40, 50]运行，最终返回的dp[5][10]结果就是预期的9。

内容的提问来源于stack exchange，提问作者Vadim Katsemba