lintcode 515. 房屋染色动态规划

Dear 丶 2023-07-24 11:56 2阅读 0赞

这里有n个房子在一列直线上，现在我们需要给房屋染色，分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同，你需要设计一种染色方案使得相邻的房屋颜色不同，并且费用最小，返回最小的费用。

费用通过一个nx3 的矩阵给出，比如cost\[0\]\[0\]表示房屋0染红色的费用，cost\[1\]\[2\]表示房屋1染绿色的费用。

样例
    样例 1:
    
    输入: [[14,2,11],[11,14,5],[14,3,10]]
    输出: 10
    解释: 第一个屋子染蓝色，第二个染绿色，第三个染蓝色，最小花费：2 + 5 + 3 = 10.
    样例 2:
    
    输入: [[1,2,3],[1,4,6]]
    输出: 3
    注意事项
    所有费用都是正整数

class Solution {
        
    public:
        /**
         * @param costs: n x 3 cost matrix
         * @return: An integer, the minimum cost to paint all houses
         */
        int minCost(vector<vector<int>> &costs) {
        
            // write your code here
            int len=costs.size();
            if(len<=0) return 0;
            vector<vector<int>> dp(len,vector<int>(3,0));
            dp[0]=costs[0];
            for (int i = 1; i < len; i++) {
        
                dp[i][0]=min(dp[i-1][1],dp[i-1][2])+costs[i][0];
                dp[i][1]=min(dp[i-1][0],dp[i-1][2])+costs[i][1];
                dp[i][2]=min(dp[i-1][1],dp[i-1][0])+costs[i][2];
            }
            return min(min(dp[len-1][0],dp[len-1][1]),dp[len-1][2]);
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，2人围观）

还没有评论，来说两句吧...

相关阅读

相关 lintcode107. 单词拆分 I动态规划

给定字符串 s 和单词字典 dict，确定 s 是否可以分成一个或多个以空格分隔的子串，并且这些子串都在字典中存在。样例样例 1: 输入: "

偏执的太偏执、/ 2023年07月25日 09:45/ 0 赞/ 7 阅读

相关 lintcode 515. 房屋染色动态规划

这里有n个房子在一列直线上，现在我们需要给房屋染色，分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同，你需要设计一种染色方案使得相邻的房屋颜色不同，并且费用最小，返回最小的

Dear 丶/ 2023年07月24日 11:56/ 0 赞/ 3 阅读

相关 lintcode 119. 编辑距离动态规划

给出两个单词word1和word2，计算出将word1 转换为word2的最少操作次数。你总共三种操作方法：插入一个字符删除一个字符替换一个字符

落日映苍穹つ/ 2023年07月18日 02:55/ 0 赞/ 44 阅读

相关 lintcode 392. 打劫房屋动态规划

假设你是一个专业的窃贼，准备沿着一条街打劫房屋。每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，且当相邻的两个房子同一天被打劫时，该系

Love The Way You Lie/ 2023年07月07日 15:58/ 0 赞/ 3 阅读

相关 lintcode395. 硬币排成线 II动态规划

有 n 个不同价值的硬币排成一条线。两个参赛者轮流从左边依次拿走 1 或 2 个硬币，直到没有硬币为止。计算两个人分别拿到的硬币总价值，价值高的人获胜。请判定先手玩

╰半橙微兮°/ 2023年07月05日 10:27/ 0 赞/ 3 阅读

相关 lintcode118. 不同的子序列动态规划

给定字符串 S 和 T, 计算 S 的所有子序列中有多少个 T. 子序列字符串是原始字符串删除一些(或零个)字符之后得到的字符串, 并且要求剩下的字符的相对位置不能改变. (

深藏阁楼爱情的钟/ 2023年07月04日 15:42/ 0 赞/ 11 阅读

相关 lintcode91. 最小调整代价动态规划

给一个整数数组，调整每个数的大小，使得相邻的两个数的差不大于一个给定的整数target，调整每个数的代价为调整前后的差的绝对值，求调整代价之和最小是多少。样例

末蓝、/ 2023年07月04日 14:08/ 0 赞/ 2 阅读

相关 lintcode 79. 最长公共子串动态规划

给出两个字符串，找到最长公共子串，并返回其长度。样例样例 1: 输入: "ABCD" and "CBCE" 输出: 2

布满荆棘的人生/ 2023年07月03日 10:32/ 0 赞/ 35 阅读

相关 lintcode76. 最长上升子序列动态规划

给定一个整数序列，找到最长上升子序列（LIS），返回LIS的长度。样例样例 1: 输入: [5,4,1,2,3] 输出: 3

灰太狼/ 2023年07月03日 08:17/ 0 赞/ 59 阅读

相关动态规划

等我有时间了，一定要把《算法导论》啃完，这本书的印刷质量实在太好了，就是烧脑子，滑稽。适合应用动态规划求解的最优化问题应该具备两个要素：最优子结构：一个问题的最优解包含

短命女/ 2022年05月17日 09:45/ 0 赞/ 354 阅读