动态编程，最小化成本？
我遇到了这个问题：
你必须乘坐一辆汽车穿过城市的N个街区，从0街区开始，到N-1街区结束。每个区块i都有一个加油站，在区块内提供天然气输送，从区块到区块以西X[i]英里和区块以东Y[i]英里。加油站只有在支付了初始金额后才能为您提供服务。C[i]。假设所有街区都位于一条笔直的道路上。给出一个算法，选择要支付的加油站，以使支付给加油站的现金最小化，并在道路上的每个位置至少有一个加油站送货。
我尝试过的事情：
蛮力-尝试了所有可能的组合，并找到了最好的一个-工作完美，但花了太长时间。- 贪婪——我试图贪婪1）成本2）距离覆盖3）每段距离的成本。
经过巨大的斗争，我得出结论，这可能是一个动态规划问题。
尝试动态编程——我试图想出一个完全没有结果的重现，我发现最难的部分是车站在两边传送。为了克服这个问题，我决定将车站“移动”到最西边的位置，并将东边的传送范围增加同样的数量——无法继续。
我发现了一个类似的问题，我想，最小成本的动态规划问题，这些问题实际上相似吗？
有人能告诉我这是否真的是一个动态规划问题，并且没有其他方法可以更有效地解决这个问题吗？如果是动态规划，你能给我一些建议吗？
Suppose N is 4
block 0 : X = 1, Y = 1, C = 2
block 1 : X = 0, Y = 2, C = 1
block 2 : X = 2, Y = 2, C = 5
block 3 : X = 1, Y = 5, C = 7
Then the result will be,
Pay block 0, 1 gas stations.
Min cost : 3
共有1个答案
据我所知，我们想要覆盖所有块的最低成本加油站集。这可以在下图中表述为最短路径问题。为每个加油站创建一个人工源、一个人工接收器和一个顶点。对于i
对于无环有向图，通常的线性时间最短路径算法的运行时间是O（n^2）。O（n）可能有改进；参见关于CS的讨论。（Yuval指定了O（n logn）time，但这只是因为他在一个不同的计算模型中工作，排序是Omega（n logn））
-
问题内容： 有什么办法以编程方式最小化JInternalFrame？ 问题答案： “图标化或取消图标化此内部框架…”
-
问题：我很难找到达到特定金额所需的最低硬币数量。我很确定这是最简单的递归方式，使用动态编程方法，我基本上应该得到Math.min（“获取ACoin”、“离开ACoin”）；不幸的是，我的代码不会终止，尽管我确实有在满足总和的条件下终止的if语句，硬币数组耗尽，或者如果总和结束。请查看下面的代码，让我知道我做错了什么，特别是为什么我的代码继续执行，直到它收到一个stackoverflow错误，尽管我
-
我目前正在尝试用Python实现动态编程，但我不知道如何设置回溯部分，使其不会重复排列。例如，一个输入应该是（6，[1,5]），预期的输出应该是2，因为有两种可能的方式来排列1和5，使它们的总和等于6。这些组合是{1,1,1,1,1}和{1,5}但是我的程序目前的工作方式，它考虑了上面显示的组合和组合{5,1}。这导致输出为3，这不是我想要的。所以我的问题是“如何防止重复排列？”。我当前的代码如下
-
1. Introduction：DP（Dynamic Programming） 定义 解决复杂问题的一种方法。将多阶过程分解为一些列单阶段问题，逐个求解，最后结合起来以解决这类过程优化问题。 同时，将这些子问题的解保存起来，如果下一次遇到了相同的子问题，则不需要重新计算子问题的解。 DP主要用于解决含有以下两点特性的问题 最优子结构：最优解能被分解为子问题，最优应用原则 覆盖子问题：子问题多次出现
-
给定一个数组，从第一个元素开始验证到达终点需要多少步。 示例：arr=[1,3,5,8,4,2,6,7,0,7,9] 1- 3个步骤。 到目前为止，我从极客那里得到了以下代码： 但是我想打印出哪些数字是最短的路径（1-3-8）。我如何调整代码来做到这一点？ 我试图创建一个j的列表，但是由于5在循环中进行了测试，所以也添加了它。 问题的链接：https://www.geeksforgeeks.org
-
我的硬币兑换动态编程实现在一些测试用例中失败，我很难找出原因： 问题陈述：给定一个数量和一个硬币列表，找出制造该数量所需的最小硬币数量。 例如： 目标金额：63 硬币列表：[1,5,10,21,25] 输出：[21,21,21] 小装饰品：https://trinket.io/python/43fcff035e