256. Paint House

256. Paint House1. 把整个图色看成是一棵树,然后dfs 根节点有三个分叉:r,g,b 第二层(g,b),(r,b),(r,g) 所以就是相当于path sum 时间复杂度应该是O(2^n) 哈哈然后LTE了 2. 动规 既然递归会超时,那就动规了 这样只有O(N)了

256.

1. 把整个图色看成是一棵树,然后dfs

根节点有三个分叉:r,g,b

第二层(g,b),(r,b),(r,g)

所以就是相当于path sum

 1     int min = Integer.MAX_VALUE;
 2     
 3     public int minCost(int[][] costs) {
 4         if(costs.length == 0 || costs[0].length == 0) {
 5             return 0;
 6         }
 7         for(int i = 0; i < 3; i++) {
 8             sum(costs, 0, 0, i);
 9         }
10         return min;
11     }
12     
13     private void sum(int[][] costs, int houseNo, int lastSum, int curColor) {
14         if(houseNo == costs.length - 1) {
15             min = Math.min(min, lastSum + costs[houseNo][curColor]);
16             return;
17         }
18         List<Integer> list = new ArrayList<Integer>(Arrays.asList(0,1,2));
19         list.remove(curColor);
20         for(int i: list) {
21             sum(costs, houseNo + 1, lastSum + costs[houseNo][curColor], i);
22         }
23     }

时间复杂度应该是O(2^n)

哈哈然后LTE了

2. 动规

既然递归会超时,那就动规了

 1     public int minCost(int[][] costs) {
 2         int len = costs.length;
 3         if(len == 0 || costs.length == 0) {
 4             return 0;
 5         }
 6         int[][] path = new int[len][3];
 7         int min = Integer.MIN_VALUE;
 8         for(int i = 0; i < 3; i++) {
 9             path[0][i] = costs[0][i];
10         }
11         for(int i = 1; i < len; i++) {
12             path[i][0] = Math.min(path[i-1][1], path[i-1][2]) + costs[i][0];
13             path[i][1] = Math.min(path[i-1][0], path[i-1][2]) + costs[i][1];
14             path[i][2] = Math.min(path[i-1][0], path[i-1][1]) + costs[i][2];
15         }
16         return Math.min(path[len-1][0], Math.min(path[len-1][1], path[len-1][2]));
17     }

这样只有O(N)了

今天的文章256. Paint House分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/47629.html

(0)
编程小号编程小号
上一篇 2023-09-04 17:46
下一篇 2023-09-04

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注