LeetCode--256. 粉刷房子（动态规划）_爱吃骨头的猫、的博客-程序员秘密

技术标签： •LeetCode

粉刷房子（动态规划）

1. 题目描述

难度：简单
在这里插入图片描述

2. 题目分析

这道题目是一道典型的动态规划问题，如果我们只把目光放在一个最少花费的身上，状态转化方程并不容易想出来，但是如果我们着眼于每一个颜色的最少花费，那么状态转化方程可以很容易地写成：

初始态

red[0] = costs[0][0] blue[0] = costs[0][0] green[0] = costs[0][0]

过程

red[i] = Min(blue[i-1], green[i-1]) + costs[i][0] blue[i] = Min(red[i-1], green[i-1]) + costs[i][1] green[i] = Min(red[i-1], blue[i-1]) + costs[i][2]

结果：

result = Min(red[n-1], blue[n-1], green[n-1])

时间复杂度为O(n).

3. C语言实现

代码如下：

int Min(int a, int b){
    
    return a<b?a:b;
}
int minCost(int** costs, int costsSize, int* costsColSize){
    
    int n = costsSize;
    if(n == 0) return 0;
    int res;
    // 申请三个内存空间用来存放每个颜色的最小花费
    int* red = (int *)malloc(sizeof(int)*n);
    int* blue = (int *)malloc(sizeof(int)*n);
    int* green = (int *)malloc(sizeof(int)*n);
    // 初始化
    red[0] = costs[0][0];
    blue[0] = costs[0][1];
    green[0] = costs[0][2];
    for(int i = 1; i < n; i++){
    
        red[i] = Min(blue[i-1], green[i-1]) + costs[i][0];
        blue[i] = Min(red[i-1], green[i-1]) + costs[i][1];
        green[i] = Min(red[i-1], blue[i-1]) + costs[i][2];
    }
    res = Min(Min(red[n-1], blue[n-1]), green[n-1]);
    // 释放数组内存空间
    free(red);
    free(green);
    free(blue);
    return res;
}

本文链接：https://blog.csdn.net/qq_42580947/article/details/105281598

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Qt中的qreal关键字说明_qt qreal_TandL520的博客-程序员秘密

在QT的手册中找到的关于qreal关键字的解释：typedef qrealTypedef for double unless Qt is configured with the-qreal float option.翻译过来是，除非用户自己配置qreal为float，否则qreal将默认为double。

二级导航--鼠标悬浮菜单出现二级菜单_飞翔的熊blabla的博客-程序员秘密

二级导航–鼠标悬浮菜单出现二级菜单&lt;!DOCTYPE html&gt;&lt;html&gt;&lt;head &gt;&lt;meta charset="utf-8"&gt;&lt;title&gt;鼠标悬浮菜单出现二级菜单&lt;/title &gt;&lt;style&gt; a{ color: #fff; text-dec

mybatis中order by排序无效问题_thankful_chn的博客-程序员秘密

mybatis中 $，# 的区别，在order by时转义导致无效

[LiteratureReview]ORB-SLAM2: an Open-Source SLAM System for Monocular, Stereo and RGB-D Cameras_local ba和full ba_GRF-Sunomikp31的博客-程序员秘密

[LiteratureReview]ORB-SLAM2: an Open-Source SLAM System for Monocular, Stereo and RGB-D Cameras出处：2017 IEEE Transactions on Robotics，（截止到2022-3-28）Google论文被引3500+；说明：ORB-SLAM2是基于ORB-SLAM[1]的工作，所以论文中对单目方法做了较少的描述，而对新添加的双目和RGB-D方法做了较多描述。Introduction完整SLA

Android 使用MD5密码加密_l6666_6666的博客-程序员秘密

在工程目录下先创建一个MD5类可以直接复制以下代码 //此处导入你的包名import java.security.MessageDigest; import java.security.NoSuchAlgorithmException;public class MD5Utils {public static String md5Password(String password)...

关于byte最高位为1时,为负数__Vanm的博客-程序员秘密

在剖析该问题前请看如下代码public static String bytes2HexString(byte[] b) {String ret = "";for (int i = 0; i String hex = Integer.toHexString(b[ i ] & 0xFF);if (hex.length() == 1) {hex = '0' + hex;}