船费问题动态规划python

以下是使用Python实现船费问题的动态规划算法的示例代码：

def min_cost(n, cost):
    dp = [0] * (n+1)
    dp[1] = cost[1]
    dp[2] = cost[1] + cost[2]
    for i in range(3, n+1):
        dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
    return dp[n]

if __name__ == '__main__':
    n = 5
    cost = [0, 1, 2, 3, 1, 2]
    print(min_cost(n, cost))  # 输出 4

其中，`n`表示船到达的港口数量，`cost`是一个长度为`n+1`的列表，表示每个港口的船费。`dp`是一个长度为`n+1`的列表，表示到达每个港口需要的最小船费。

首先，我们初始化`dp[1]`和`dp[2]`为第一个港口和第二个港口的船费之和。接着，我们遍历每个港口，使用动态规划的思想，通过比较到达当前港口的两种路径（从前一个港口或从前两个港口）的船费之和，选择较小的值加上当前港口的船费更新`dp`列表。最终，`dp[n]`即为到达最后一个港口需要的最小船费。

相关问题

船费问题动态规划java

本题可以使用动态规划来解决。首先，我们可以考虑定义状态。设$f[i][j]$表示到第i个城市，并且船费用不超过j元的最小花费。那么最终的答案即为$f[N][K]$，其中N表示城市数量，K表示船费的上限。接下来我们考虑状态转移方程。

对于第i个城市，我们可以选择不乘坐船或者选择乘坐某一艘船。如果我们不乘坐船，那么$f[i][j]$就等于$f[i-1][j]$；如果我们选择乘坐某一艘船，那么$f[i][j]$就等于$f[i-1][j-cost[i][k]]+fee[i][k]$，其中cost[i][k]表示从第i-1个城市到第i个城市乘坐第k艘船的花费，fee[i][k]表示在第i个城市乘坐第k艘船的花费。因此，状态转移方程为：

$f[i][j]=\min(f[i-1][j],f[i-1][j-cost[i][k]]+fee[i][k])$

最后，我们可以使用一维数组来优化空间，因为在状态转移过程中只需要用到f[i-1]的值，因此我们可以将二维数组压缩成一维数组。具体实现细节请见下方的Java代码。

Java代码：

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); //城市数量
        int m = in.nextInt(); //船的数量
        int k = in.nextInt(); //船费的上限
        int[][] cost = new int[n + 1][m + 1]; //从第i-1个城市到第i个城市乘坐第j艘船的花费
        int[][] fee = new int[n + 1][m + 1]; //在第i个城市乘坐第j艘船的花费
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cost[i][j] = in.nextInt();
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                fee[i][j] = in.nextInt();
            }
        }
        int[] f = new int[k + 1]; //一维数组
        Arrays.fill(f, Integer.MAX_VALUE / 2); //初始化为最大值的一半
        f[0] = 0; //初始状态
        for (int i = 1; i <= n; i++) {
            for (int j = k; j >= 0; j--) {
                for (int p = 1; p <= m; p++) {
                    if (j >= cost[i][p]) {
                        f[j] = Math.min(f[j], f[j - cost[i][p]] + fee[i][p]);
                    }
                }
            }
        }
        System.out.println(f[k]); //输出答案
    }
}