动态规划涂墙问题java
时间: 2024-01-25 17:13:15 浏览: 29
动态规划涂墙问题是一个经典的问题,可以使用动态规划算法来解决。下面是一个Java的动态规划涂墙问题的实现示例:
```java
public class WallPainting {
public static int minCost(int[][] costs) {
if (costs == null || costs.length == 0) {
return 0;
}
int n = costs.length;
int[][] dp = new int[n][3];
dp[0][0] = costs[0][0];
dp[0][1] = costs[0][1];
dp[0][2] = costs[0][2];
for (int i = 1; i < n; i++) {
dp[i][0] = costs[i][0] + Math.min(dp[i-1][1], dp[i-1][2]);
dp[i][1] = costs[i][1] + Math.min(dp[i-1][0], dp[i-1][2]);
dp[i][2] = costs[i][2] + Math.min(dp[i-1][0], dp[i-1][1]);
}
return Math.min(Math.min(dp[n-1][0], dp[n-1][1]), dp[n-1][2]);
}
public static void main(String[] args) {
int[][] costs = {{17, 2, 17}, {16, 16, 5}, {14, 3, 19}};
int minCost = minCost(costs);
System.out.println("The minimum cost of painting the walls is: " + minCost);
}
}
```
这段代码中,`costs`是一个二维数组,表示每种颜色涂在每个墙上的成本。`dp`是一个二维数组,用来保存每个状态下的最小成本。通过动态规划的思想,我们可以从第一行开始逐行计算每个状态的最小成本,直到最后一行。最后,返回最后一行中的最小值,即为涂墙的最小成本。