ACM 关于动态规划的疑问

来源：学生作业帮编辑：作业帮分类：数学作业时间：2024/05/22 00:26:30

ACM 关于动态规划的疑问
某旅游城市在长江边开辟了若干个旅游景点.一个游船俱乐部在这些景点都设置了游船出租站,游客可在泽泻游船出租站租用游船,并在下游的任何一个游船出租站归还游船,从一个悠长出租站到下游的游船出租站间的租金明码标价.你的任务是为游客计算从起点站到终点之间的最少租船费用.
输入样例
3
2 3 6 //从起点到第1 ,2 ,3个站的租金,下同
1 3
2
3
4 7 9
4 5
6
输出样例
case 1:5
case 2:9
一个DP的思路是（当然不是最好的DP方法）
m[i][j]=min {m[i][k]+m[k][j] ,r[i][j] }
这是书上的方法当然是对的
我的问题是第二个m[k][j]改成r[k][j],也就是认为k到j是直达的
m[i][j]=min {m[i][k]+r[k][j] ,r[i][j] }
如何判断算法正确性?

第二种做法完全正确.假设在“从i到j花费最少价钱的路线”中,j前的一站是k,那么这种做法就必然可以取到正确答案.因为在i到j的最优路线中,从i到k的路线选取也必然是最优的.
另外必须理解的是,采取第二种做法后,当i!=0时,m[i][j]既不用求得,也不需要用它推导其它量,m[i][j]只有当i=0时才有用,所以m数组直接简化为一维就可以了,所以第二种方程的实质就是最好的方法.时间复杂度O(N^2),不可能继续优化.
是一道最简单的DP,没什么难的.算法正确性可以严格证明,但在ACM里一般找找反例多想一想就行了

ACM DP动态规划题：通过加入字符,使一字符串对称,求加入字符的最小个数. ACM解题报告我想要一个ACM的题型总结,最好题都是北大平台上的比如：标明题号（最好都是北大平台上的题目）动态规划 c语言数字三角形的动态规划 ACM动态规划问题刘汝佳的算法白皮书上DP三角形求最大和那道题,书上有3中方法,第一种是递归计算,第二种递推计算,第三种动态规划算法关于ACM竞赛的问题, 求一道动态规划题的解答思路以及状态方程数学建模中规划的分类时常有什么线性规划和非线性规划动态规划非动态规划多目标规划单目标规划到底该怎么具体的给数学 ACM一道动态规划题只用告诉我大体思路即可,要清楚哈.题意如下：任意给定一些数a i （个数＜1000000）,再给一个关于简单的C语言的ACM, 西北工业大学运筹学真题：1.试述建立动态规划数学模型的步骤及应注意的问题,并说明动态规划的求解方法有关于“宇宙空间”的疑问