从暴力递归到动态规划(2)小乖,你也在为转移方程而烦恼吗?

前引:继上篇我们讲到暴力递归的过程,这一篇blog我们将继续对从暴力递归到动态规划的实现过程,与上篇类似,我们依然采用题目的方式对其转化过程进行论述。

上篇博客:https://blog.csdn.net/m0_65431718/article/details/129604874?spm=1001.2014.3001.5502

一.n皇后问题

八皇后问题是十九世纪著名的数学家高斯于1850年提出的。问题是:在n×n的棋盘上摆放n个皇后,使任意两个皇后都不能处于同一行、同一列或同一斜线上。

我们的解题思路如下:采用暴力递归,既然要求任意两个皇后不能在同一行和同一列和同一斜线,我们依次对这三者进行讨论:①同一行:每一层递归代表一行,我们只要保证在每一层递归中只放置一个皇后即可②同一列:按照题目的要求,我们在访摆放第n层的皇后时,要保证它和前面n-1等皇后都不冲突,这就意味着我们在进行下一层递归的时候仍能有方法访问前面皇后摆放的位置:我们的第一考虑对象当然是数组,但是比较巧妙的是它是一个n*n的棋盘,第一个n代表行,第二个n代表列,我们只需要建立一个长度为n的一维数组,下标代表第几行,下标对应的数组元素代表列,作为参数带入到下一层递归中,斜线也是如此,我们详细展开说说列和斜线的要求:对于列来说,我们要遍历缓存,使前面的缓存和当前列不相等即为不冲突,对于斜线的要求来说,对于一个正方形棋盘,我们其实很容易想到的是直线的斜率为1,也就是说两个元素行的变化如果等于列的变化,我们可以说在同一条斜线上。我们根据思路给出code:

public class NEmpress {
    public static void main(String[] args) {
        //创建date
        int n=4;
        int[]data=new int[n];
        System.out.println(process(data, 0, n));
       

    }
    //创建递归过程
    public static int process(int[]data,int i,int n){
        //判断出口条件:共有n个元素,一旦当前行越过了n-1,则说明成功
        if(i==n){
            return 1;
        }
        //循环处理每一列
        //如果没结束
        int res=0;
        for(int j=0;j<n;++j){
            //判断当前元素是否有效
            if(isValid(data,i,j)){
                data[i]=j;
                //进入下一层递归
               res+= process( data, i+1, n);
            }
        }
        return res;
    }
 private static boolean isValid(int[] data, int i, int j) {
        //在data中检验是否存在
        for(int k=0;k<i;++k){
            //第一个是判断从0到i-1行中列的元素是否相等,第二个是判断是否在同一斜线
            if(data[k]==j||(Math.abs(i-k)==Math.abs(j-data[k]))){
                return false;
            }
        }
        return true;
    }
}

如果不改变问题的实现思路,很难去实现大的效率提升,但是考虑不同的方法仍能在一定程度上提升效率(常数级提升):采用位运算,总体的实现逻辑和之前的暴力递归完全相同,但是就具体细节做出了一定的改动,我们给出递归的核心代码,并改动进行解释说明:

limit:是位数限制,对于行列数为N的棋盘,limit的限制是:对于前N个二进制位数均为1,对于N行列的棋盘而言,前N个二进制位代表棋盘的每一行(第一个二进制位代表第一行,第二个代表第二行........)

①col:对于每次摆放个皇后,就将这个二进制位置变为1,表示这个二进制位不能摆放皇后了

②leftLim:左斜线限制,如果leftLim为1,代表对于当前行来说,这个位置不能摆放皇后了。

③RightLim:右斜线限制,如果RightLim为1,同样对于当前行来说,这个位置不能摆放皇后了。

④limit==col:代表col前N个二进制位都是1,表示N个皇后都已经摆放好了,游戏结束,退出递归

⑤limit&(~(col|leftLim|rightLim)):pos是在每一行中能选择的列

⑥ mostRight=pos&(~pos+1):取出最右边的一位

⑦ pos-=mostRight:将最右边的位置从可选择的位数中去除,使当前行不能放置皇后

⑧while(pos!=0) 循环当前行中能选择的位置

⑨res+= process2(limit,col|mostRight,(leftLim|mostRight)<<1, (rightLim|mostRight)>>>1):循环下一层

public static int process2(int limit,int col,int leftLim,int rightLim){
        //递归出口
    if(limit==col){
        return 1;
    }
    //计算能放的位置:
    int pos= limit&(~(col|leftLim|rightLim));
    int mostRight=0;
   int res=0;
    //检验是否能递归
    while(pos!=0){
        //找最右的位置
         mostRight=pos&(~pos+1);
 
        pos-=mostRight;
      res+=  process2(limit,col|mostRight,(leftLim|mostRight)<<1, (rightLim|mostRight)>>>1);
    }
    return res;

我们对代码中的几个点进行解释说明:

三.机器人走路问题:(从暴力递归到动态规划的实践)

问题要求如下:

1.假设有排成一行的n个位置记为1-N,N一定大于等于2
2.开始时机器人在m位置上,m一定是1-N中的一个
3.机器人要在规定的步数到达指定的终点,计算到达指定终点的路线有多少条
4.如果机器人来到1位置只能往右来到2位置
5.如果机器人来到N位置只能往左来到N-1位置
6.如果机器人在其他位置,则机器人可以往右也可以往左

对于暴力递归,实现思路就相对比较简单:对于当前位置而言,如果位置是1,他只能选择2,如果在2-N-1的位置,他可以向左和向右走,如果在N位置,只能往N-1的位置走,不断走,直到剩余步数为0,判断是不是要求的位置,然后返回结果。

我们给出关于暴力递归的代码:

public int walking(int N,int cur,int rest,int P){
        //编写递归出口
        if(rest==0){
            if(cur==P){
                return 1;
            }else {
                return 0;
            }
        }
        //排除特殊情况,在0位置处:只能往后走
        if(cur==1){
            return walking(N, cur+1, rest-1, P);
        }
        //在最后一个位置,只能往前走
        if(cur==N){
            return walking(N, cur-1, rest-1, P);
        }
        //在中间,可以往前往后走
        return walking(N, cur-1, rest-1, P)+walking(N, cur+1, rest-1, P);


        }

为什么说这是从暴力递归到动态规划的实践开始呢?我们对此进行解释:

我们能在暴力递归的基础上修改为动态规划,什么是动态规划呢?是将暴力递归中重复计算的过程转化为缓存,从而降低暴力递归中重复计算的次数,转而从相关缓存中获取,是一种典型的空间换时间的策略,对于动态规划而言,其实最难的部分是写出关于动态规划的转移方程。

对这道题来说,这种动态规划的类型是记忆性搜索:如果这个位置有缓存,就直接返回缓存结果,否则递归。

动态规划的的code如下:

public int walkCache(int N,int cur,int rest ,int [][]dp,int P){
        if(dp[cur][rest]!=-1){
            return dp[cur][rest];
        }
        if(rest==0){
            dp[cur][rest]=cur==P?1:0;
            return dp[cur][rest];
        }
        if(cur==1){
            dp[cur][rest]=walkCache(N, cur+1, rest-1, dp,P);
            return dp[cur][rest];
        }
        if(cur==N){
            dp[cur][rest]=walkCache(N, cur-1, rest-1, dp,P);
            return dp[cur][rest];
        }
            return dp[cur][rest]=walkCache(N, cur-1, rest-1, dp,P)+walkCache(N, cur+1, rest-1,dp, P);
        }
    }

四.零和博弈问题:

问题描述:

思路:对于A而言,作为先手,他一定在纵观全局后选择对自己最有利的计划,而B作为后手,只能在A 选择之后在此基础上选择对自己最友好的计划和策略,换句话说,B选择的只能是A选择剩下的

所以我们需要设计两个函数,一个是先手函数,选择其中相对自己而言最优的策略,即为选择自己能选的棋中的最大值,而同样需要设计一个后手函数,它的作用是:在后手参与下选择相对较小的选择(只能选择A选剩下的

我们给出code:

package violencerecursion;

/**
 * @author tongchen
 * @create 2023-03-21 16:09
 */
public class GameWin {
    public static void main(String[] args) {
        GameWin gameWin = new GameWin();
        int[]arr={1,100,1};
        System.out.println(gameWin.win(arr));
    }
    public int win(int[]arr){
        //零和博弈问题,解题思路:先手的人拿最优的选择,后手的人只能被迫接收最差的结果
        int left=0;
        int right= arr.length-1;
       return Math.max(f(arr, 0, arr.length-1),s(arr, 0, arr.length-1));
    }

    private int f(int[] arr, int left, int right) {
        //递归出口
        if(left==right){
            return arr[left];
        }
        //选择已知策略中最优的选择
        return Math.max(arr[left]+s(arr,left+1,right),arr[right]+s(arr,left,right-1));

    }

    private int s(int[] arr, int left, int right) {
        if(right==left){
            return 0;
        }
        //B相当于从第二个棋子先选择(因为第一个棋子肯定被A选走了,B先手选第二个棋子)
        //但是这种情况下B只能选择在A纵观全局后选择最优策略之后被迫选择劣的选择(即最小值)
        return Math.min(f(arr, left+1, right),f(arr, left, right-1));
    }
}

后续会更新关于动态规划的转移方程的编写思路过程,希望大家能持续关注捏~

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/3248.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

看完这篇 教你玩转渗透测试靶机vulnhub——My File Server: 1

Vulnhub靶机My File Server: 1渗透测试详解Vulnhub靶机介绍&#xff1a;Vulnhub靶机下载&#xff1a;Vulnhub靶机安装&#xff1a;Vulnhub靶机漏洞详解&#xff1a;①&#xff1a;信息收集&#xff1a;②&#xff1a;FTP匿名登入&#xff1a;③&#xff1a;SMB共享服务&#xf…

【微信小程序】-- 使用 Git 管理项目(五十)

&#x1f48c; 所属专栏&#xff1a;【微信小程序开发教程】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &…

【Docker】Compose容器编排LNMP上云

文章目录什么是Docker-Compose下载安装官网官网下载安装卸载Compose核心概念一文件两要素三个步骤Compose常用命令DjangoMysqlRedisNginx部署部署架构构建django容器 - - - dockerfile编写构建Nginx容器docker-compose 编排容器Django项目配置custom_webmysql容器redis容器Djan…

一文看懂数据仓库

数据仓库数据仓库的概念数据仓库的主要特征数据仓库的分层数据仓库的分层介绍原始数据层&#xff1a;ODS&#xff08;Operational Data Store&#xff09;数据仓库层&#xff1a;DW&#xff08;Data Warehouse&#xff09;数据明细层&#xff1a;DWD&#xff08;Data Warehouse…

邪恶的想法冒出,立马启动python实现美女通通下

前言 嗨喽~大家好呀&#xff0c;这里是魔王呐 ❤ ~! 完整源码、python资料: 点击此处跳转文末名片获取 当我在首页刷到这些的时候~ 我的心里逐渐浮现一个邪念&#xff1a;我把这些小姐姐全都采集&#xff0c;可以嘛&#xff1f; 答案当然是可以的~毕竟就我这技术&#xff0c…

【Java|golang】45. 跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说&#xff0c;如果你在 nums[i] 处&#xff0c;你可以跳转到任意 nums[i j] 处: 0 < j < nums[i] i j < n 返回到达 nums[n - 1] 的最…

不会写SQL?ChatGPT 来帮你

想必当前最火的软件就是ChaGPT了&#xff0c;它是一款基于人工智能技术的大型语言模型,在数据库方面&#xff0c;ChaGPT可以被用来进行自然语言处理&#xff0c;实现自然语言查询和分析数据库。通过将ChaGPT与数据库集成&#xff0c;可以使得数据库更加智能化&#xff0c;提高数…

【2023】Kubernetes-网络原理

目录kubernetes网络模型kubernetes网络实现容器到容器之间通信Pod之间的通信Pod到Service之间的通信集群内部与外部组件之间的通信开源容器网络方案FlannelCalicokubernetes网络模型 Kubernetes网络模型设计的一个基础原则是&#xff1a;每个Pod都拥有一个独立的IP地址&#x…

【Android -- 软技能】《软技能:代码之外的生存指南》之好书推荐(一)

前言 这是一本由美国的一个软件开发人员写的&#xff0c;但书中除了有 Java 、C# 几个单词外&#xff0c;没有一行代码。 因为这本书讲的是代码之外的东西。 文章目录结构&#xff1a; 1. 职业 从业心态&#xff1a;说白了就是要有责任心&#xff0c;把每份工作要当成是自…

【国产FPGA】国产FPGA搭建图像处理平台

最近收到了高云寄过来的FPGA板卡&#xff0c;下图&#xff1a;来源&#xff1a;https://wiki.sipeed.com/hardware/zh/tang/tang-primer-20k/primer-20k.htmlFPGA主要参数:FPGA型号参数GW2A-LV18PG256C8/I7逻辑单元(LUT4) 20736寄存器(FF) 15552分布式静态随机存储器S-SRAM(bit…

Python+Yolov5道路障碍物识别

PythonYolov5道路障碍物识别如需安装运行环境或远程调试&#xff0c;见文章底部个人QQ名片&#xff0c;由专业技术人员远程协助&#xff01;前言这篇博客针对<<PythonYolov5道路障碍物识别>>编写代码&#xff0c;代码整洁&#xff0c;规则&#xff0c;易读。 学习与…

蓝桥杯刷题冲刺 | 倒计时15天

作者&#xff1a;指针不指南吗 专栏&#xff1a;蓝桥杯倒计时冲刺 &#x1f43e;马上就要蓝桥杯了&#xff0c;最后的这几天尤为重要&#xff0c;不可懈怠哦&#x1f43e; 文章目录1.年号字串2.裁纸刀3.猜生日1.年号字串 题目 链接&#xff1a; 年号字串 - 蓝桥云课 (lanqiao.c…

Java 网络编程入门

文章目录一、网络编程入门1. 网络编程三要素2. IP 地址3. InetAddress4. 端口5. 协议二、UDP 通信程序1. UDP 发送数据2. UDP 接收数据3. UDP 案例三、TCP 通信程序1. TCP 发送数据2. TCP 接收数据3. 服务器给出反馈4. 客户端录入键盘数据5. 服务器数据写入文件6. 客户端数据来…

Ubuntu使用vnc远程桌面【远程内网穿透】

文章目录1.前言2.两台互联电脑的设置2.1 Windows安装VNC2.2 Ubuntu安装VNC2.3.Ubuntu安装cpolar3.Cpolar设置3.1 Cpolar云端设置3.2.Cpolar本地设置4.公网访问测试5.结语1.前言 记得笔者刚刚开始接触电脑时&#xff0c;还是win95/98的时代&#xff0c;那时的电脑桌面刚迈入图形…

C++三种继承方式

C继承的一般语法为&#xff1a;class 派生类名:&#xff3b;继承方式&#xff3d; 基类名{派生类新增加的成员};继承方式限定了基类成员在派生类中的访问权限&#xff0c;包括 public&#xff08;公有的&#xff09;、private&#xff08;私有的&#xff09;和 protected&#…

Python|蓝桥杯进阶第五卷——数论

欢迎交流学习~~ 专栏&#xff1a; 蓝桥杯Python组刷题日寄 蓝桥杯进阶系列&#xff1a; &#x1f3c6; Python | 蓝桥杯进阶第一卷——字符串 &#x1f50e; Python | 蓝桥杯进阶第二卷——贪心 &#x1f49d; Python | 蓝桥杯进阶第三卷——动态规划 ✈️ Python | 蓝桥杯进阶…

Linux基本命令

相比Windows系统而言&#xff0c;在一般的企业开发中&#xff0c;使用linux系统无疑是更加广泛的&#xff0c;因此掌握常见的linux基本命令于我们来说是必要的&#xff0c;本文就是对Linux基本命令的简单介绍。 ls 列出当前目录下&#xff0c;所包含的目录及文件&#xff1b; …

学习系统编程No.9【文件操作】

引言&#xff1a; 北京时间&#xff1a;2023/3/23/6:34&#xff0c;可能是昨天充分意识到自己的摆烂&#xff0c;所以今天起的比较早一点吧&#xff01;昨天摆烂的头号原因&#xff0c;笔试强训&#xff0c;加上今天4节课&#xff0c;可以说一整天都是课&#xff0c;所以能不能…

【CE进阶】lua脚本使用

▒ 目录 ▒&#x1f6eb; 导读需求开发环境1️⃣ 脚本窗口Lua ScriptLua EngineAuto assemble2️⃣ 全局变量3️⃣ 进程当前打开的进程ID系统的进程列表系统的顶部窗口列表4️⃣ 线程5️⃣ 输入设备6️⃣ 屏幕7️⃣ 剪贴板&#x1f6ec; 文章小结&#x1f4d6; 参考资料&#x…

算法的时间复杂度和空间复杂度

目录 1 如何衡量一个算法的好坏 2.时间复杂度 2.1 时间复杂度的概念 2.2 大O的渐进表示法 2.3常见代码举例 2.3.1 Func2 O(N) 2.3.2 Func3 O(MN) 2.3.3 Func4 O(1) 2.3.4 Func5 strchr O(N) 2.3.5 Func6 冒泡排序 O(N^2) 2.3.6 Func7 二分…