首页 > 其他分享 >dfs思想方式

dfs思想方式

时间:2023-11-22 20:34:08浏览次数:30  
标签:return 思想 方式 int res memo dfs grid

dfs 深度优先搜索:一条路走到黑

基本模型:

Returntype dfs(参数) {
  判断边界(返回)
  扩展状态 dfs下一步
  返回
}

dfs + 记忆返回值 = 记忆化搜索

 

 

class Solution {
public:
    int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> memo(m, vector<int>(n, -1));

        function<int(int, int)> dfs = [&](int i, int j) ->int {
            if(i == m - 1) return grid[i][j];
            if(memo[i][j] >= 0) return memo[i][j];
            int res = INT_MAX;
            for(int k = 0; k < n; k ++ ) {
                res = min(res, dfs(i + 1, k) + moveCost[grid[i][j]][k] + grid[i][j]);
            }
            memo[i][j] = res;
            return res;
        };

        int res = INT_MAX;
        for(int j = 0; j < n; j ++ ) {
            res = min(res, dfs(0, j));
        }

        return res;
    }
};

 

标签:return,思想,方式,int,res,memo,dfs,grid
From: https://www.cnblogs.com/zk6696/p/17850215.html

相关文章

  • acwing 第 130 场周赛  (前缀和,dfs,对不同边的处理)
      #include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<climits>usingnamespacestd;typedeflonglongLL;constintN=5010;intn;inta[N];LLs[N];LLget(intl,intr){return......
  • 关于搭建自动直播平台的方式
    前期准备工作准备一台轻量应用服务器,配置如下图所示:大概每个月65元左右准备需要直播的视频,规格为1080p30帧,必须是MP4格式的视频文件环境安装登录命令窗口后运行以下指令安装screenyum-yinstallscreen安装screen完成后,使用命令screen-Sstream进入screen窗口......
  • filerun docker方式安装(debian arm64, tinkerboard2s类似树莓派)
    启动mysqldockerrun-p3366:3306--namemysql57--privileged=true-eMYSQL_ROOT_PASSWORD=12345-v/mnt/docker/varlibmysql:/var/lib/mysql-dliupeng0518/mysql:5.7-arm64#redis命令dockerrun-itd--nameredis--privileged=true-p6380:6379redis--requir......
  • 陌陌头像留二维码隐藏技术,微信号,双头像生成工具,“codeA”方式开源
    正常情况下我们在陌陌头像留二维码会被系统检测到的,因为它识别到了这是二维码是,就算不封号对账号权重也有营销,但是一些人想在陌陌做一些产品,比如足浴、保健品之类的,想在陌陌引流,那么留二维码头像不封号的实现就非常重要了,我制作的这个工具可以生成干扰码,就是二维码生成干扰码导致......
  • WinForm上位机常用的通信方式有以下几种:
    WinForm上位机常用的通信方式有以下几种:串口通信:使用SerialPort类实现。示例代码:usingSystem;usingSystem.IO.Ports;publicclassSerialPortExample{privateSerialPort_serialPort;publicSerialPortExample(stringportName,intbaudRate){......
  • DB2存储过程,输出数据集的几种方式汇总
    1----------------1、直接输出数据集-------------------2CREATEORREPLACEPROCEDURE"BI_DM"."SP_XINGUANQUERY"(3startdatevarchar(20)4,enddatevarchar(20)5,querydiagnamevarchar(64)6)7dynamicresultsets18LAN......
  • loj144&145 dfs序+树状数组/线段树
    https://loj.ac/p/144https://loj.ac/p/145两题非常相似,一题的权值修改是在点上的,一题的权值修改是在整棵子树上的。首先我们要了解dfs序,并记录每个节点的子树大小sz,对于一个节点,在dfs序上sz长的区间全都是他的子节点以及他自己。所以我们将一棵树映射到了一个区间上,并且可......
  • WPF --- 如何以Binding方式隐藏DataGrid列
    引言如题,如何以Binding的方式动态隐藏DataGrid列?预想方案像这样:先在ViewModel创建数据源People和控制列隐藏的IsVisibility,这里直接以MainWindow为DataContextpublicpartialclassMainWindow:Window,INotifyPropertyChanged{publicMainWindow(){......
  • kvm-虚拟机登陆方式VNC、virsh console
    阅读目录(Content)1、虚拟机多,VNC登陆问题2、多虚拟机,VNC登陆的实战3、使用virsh console登陆实战3.1、需求3.2、虚拟机开启支持console 3.3、登陆测试3.4、退回virshconsole方法回到顶部(gototop)1、虚拟机多,VNC登陆问题当我们虚拟机过多的时候,如果想用vn......
  • docker和docker-compose生产的容器,不在同一个网段,解决方式
    在实际项目中,使用dockerrunxxXx 和docker-composeup-d不在同一个网段,一个是默认是172.17.x.x, 另一个是172.19.x.x。为解决这个问题需要自定义一个网络,我命名为“my-bridge”首先熟悉几条命令:dockernetworkls或者dockernetworklist 查看当前的docker网络......