当前位置: 首页 > news >正文

21.2:象棋走马问题

请同学们自行搜索或者想象一个象棋的棋盘,
然后把整个棋盘放入第一象限,棋盘的最左下角是(0,0)位置
那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域
给你三个 参数 x,y,k
返回“马”从(0,0)位置出发,必须走k步
最后落在(x,y)上的方法数有多少种?

一:暴力方法

	/*** 暴力方法*/public static int jump(int a, int b, int k) {return process(a, b, k, 0, 0);}//返回落在a,b上并且走k步的方法数public static int process(int a, int b, int k, int x, int y) {if (k == 0) {return (x == a && y == b) ? 1 : 0;}//9行10列if (x < 0 || y < 0 || x > 9 || y > 8) {return 0;}int p1 = process(a, b, k - 1, x + 2, y + 1);int p2 = process(a, b, k - 1, x + 1, y + 2);int p3 = process(a, b, k - 1, x + 2, y - 1);int p4 = process(a, b, k - 1, x + 1, y - 2);int p5 = process(a, b, k - 1, x - 2, y + 1);int p6 = process(a, b, k - 1, x - 1, y + 2);int p7 = process(a, b, k - 1, x - 2, y - 1);int p8 = process(a, b, k - 1, x - 1, y - 2);return p1 + p2 + p3 + p4 + p5 + p6 + p7 + p8;}

表格法

在这里插入图片描述

有三个变化的变量分别是:x,y,k 所以是一个三维的表格。

当层数是0的时候,只有(a,b,0)处是1,其他位置是0。

我还发现上一层是严格的依赖下一层的。上一层的每一个表格严格依赖下一层对应的八个表格(不越界的话)。

那填表的顺序就是由下往上一层一层的填表。

注意最后返回的是:dp[][][][] [ 0 ] [ 0 ] [ k ] 而不是 dp[][][][] [ a ] [ b ] [ k ] —> 表格法可以看成是递归的归过程。最终归的终点是最开始传入

进方法的起点位置。

本题可以想象一下:刚开始一定是(0,0,k) 之后向下层依赖,辐射到下一层的8个位置(不越界),之后下一层的8个位置继续向下层辐射8个位置,直到辐射到最底层,如果辐射到的最低层包含着(a,b,0)就算可以到达目标位置。

	/*** 迭代法*/public static int dp(int a, int b, int k) {//这里需要考虑k以及k==0时的情况,所以取k的范围是k+1个int[][][] dp = new int[10][9][k + 1];//依赖关系是:上层依赖下层,最终返回最上层,所以从下向上构建dp[a][b][0] = 1;for (int plie = 1; plie <= k; plie++) {//这一层的每个数都依赖下一层。for (int x = 0; x < 10; x++) {for (int y = 0; y < 9; y++) {int p1 = pick(dp, x + 2, y + 1, plie - 1);int p2 = pick(dp, x + 1, y + 2, plie - 1);int p3 = pick(dp, x + 2, y - 1, plie - 1);int p4 = pick(dp, x + 1, y - 2, plie - 1);int p5 = pick(dp, x - 2, y + 1, plie - 1);int p6 = pick(dp, x - 1, y + 2, plie - 1);int p7 = pick(dp, x - 2, y - 1, plie - 1);int p8 = pick(dp, x - 1, y - 2, plie - 1);dp[x][y][plie] = p1 + p2 + p3 + p4 + p5 + p6 + p7 + p8;}}}return dp[0][0][k];//注意返回的是(0,0,k)这个坐标}public static int pick(int[][][] dp, int x, int y, int pile) {if (x < 0 || y < 0 || x > 9 || y > 8) {return 0;} else {return dp[x][y][pile];}}

相关文章:

21.2:象棋走马问题

请同学们自行搜索或者想象一个象棋的棋盘&#xff0c; 然后把整个棋盘放入第一象限&#xff0c;棋盘的最左下角是(0,0)位置 那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域 给你三个 参数 x&#xff0c;y&#xff0c;k 返回“马”从(0,0)位置出发&#xff0c;必须走k步 …...

【CSS】手写 Tooltip 提示组件

文章目录 效果示例代码实现 效果示例 代码实现 <!DOCTYPE html> <html><head><meta charset"utf-8"><title>一颗不甘坠落的流星</title><style>body {padding: 120px;}.tooltip {position: relative;display: inline-blo…...

MySQL DDL语法

MySQL DDL语法 DDL简介 MySQL DDL&#xff08;Data Definition Language&#xff09;是用于定义和管理数据库结构的语言。它包括创建、修改和删除数据库、表、视图、索引和其他数据库对象的语句。DDL语法的重要性如下&#xff1a; 数据库结构定义&#xff1a;DDL语句用于创建…...

Git 绑定账号 和clone

一:环境: 下载安装完成Git,在桌面或文件夹下(在你将要保存代码的位置)右击可以看到Git Bash Here,点击可以进入黑窗口 二:配置公钥 1.查看当前状态(如果已绑定,且知道密码可以登陆,可以直接获取SSH公钥并配置即可拉取代码) git config --list 2.配置全局git用户名和邮箱 …...

ftp和sftp区别,以及xftp的使用

网上找链接找的很辛苦对吧&#xff01; 网上下载的破解版还不用。而且用没多久又说要更新了&#xff0c;又得重新找。 这下直接把官方免费获取链接发给你&#xff0c;就不用在被这种事情麻烦了。 家庭/学校免费 - NetSarang Website (xshell.com):家庭/学校免费 - NetSarang W…...

C++ 编程入门(一)—— Hello World

C 是什么环境搭建第一个 C 程序本篇结语 C 是什么 C 是一种面向对象的计算机程序设计语言&#xff0c;由美国 AT&T 贝尔实验室的 Bjarne Stroustrup 在 20 世纪 80 年代初期发明并实现&#xff08;最初这种语言被称作 “C with Classes” 带类的 C 语言&#xff09;。它是一…...

openlayers系列:加载arcgis和geoserver在线离线切片

https://www.freesion.com/article/1751396517/ 1.背景 有个项目需要使用openlayer加载各种服务上发布的数据&#xff0c;坐标系也不同&#xff0c;我们都知道openalyer默认可以加载EPAG:3857,要加载4490的坐标系的数据需要重新定义一下&#xff0c;之后再加载。一想起要重新…...

《人工智能安全》课程总体结构

1 课程内容 人工智能安全观&#xff1a;人工智能安全问题、安全属性、技术体系等基本问题进行了归纳整理。人工智能安全的主要数据处理方法&#xff0c;即非平衡数据分类、噪声数据处理和小样本学习。人工智能技术赋能网络空间安全攻击与防御&#xff1a;三个典型实例及攻击图…...

unity关于匀速移动某些值的方法

可能很多人会用到Verctor3.Lerp、Mathf.LerpUnclamped等等 这种其实不是匀速 看一下这个整体差不多的逻辑 public static float Lerp(float a, float b, float t){return a (b - a) * t;};这个逻辑就是&#xff0c;从a值到b值&#xff0c;返回一个a值加&#xff08;b值-a值&…...

解决VScode下载太慢的问题记录

最近突然想重新下载vscoded便携免安装版&#xff0c;发现下载很慢&#xff0c;于是乎查询一下&#xff0c;以便记录 下载地址 VScode官方网站&#xff1a; https://code.visualstudio.com/ 根据个人的需求选择下载&#xff0c;页面加载下载需要等一会&#xff0c; 然后就会…...

Gitlab服务器备份恢复及系统升级

居安思危&#xff0c;思则有备&#xff0c;有备无患。 基于此&#xff0c;申请了一个测试服务器&#xff0c;准备先安装同版本服务器&#xff0c;按照最新的数据进行恢复&#xff0c;然后再将现在的服务器升级到Gitlab的最新版本&#xff0c;记录一下完整的过程&#xff0c;以…...

docker入门讲解

目录 第 1 章 Docker核心概念与安装 为什么使用容器? Docker是什么 Docker设计目标 Docker基本组成 容器 vs 虚拟机 Docker应用场景 Linux 安装 Docker 第 2 章 Docker镜像管理 镜像是什么 镜像从哪里来? 镜像与容器联系 镜像常用管理命令 镜像存储核心技术:联…...

【Matlab】基于卷积神经网络的数据回归预测(Excel可直接替换数据))

【Matlab】基于卷积神经网络的数据回归预测(Excel可直接替换数据) 1.模型原理2.数学公式3.文件结构4.Excel数据5.分块代码6.完整代码7.运行结果1.模型原理 基于卷积神经网络(Convolutional Neural Network,CNN)的数据回归预测是一种常见的机器学习方法,适用于处理具有空…...

在Springboot集成Activiti工作流引擎-引入、调用,测试【基础讲解】

工作流 通过计算机对业务流程自动化执行管理 他主要解决的是使在多个参与者之间按照某种“预定义规则”自动进行传递稳定 信息或任务的过程 通俗来讲 业务上一个玩着的审批流程 比如请假&#xff0c;出差 外出采购等 工作流引擎就是来解决流程问题的 提高我们的工作效率 如果…...

Java书签 #解锁MyBatis的4种批量插入方式及ID返回姿势

1. 今日书签 项目开发中&#xff0c;我们经常会用到单条插入和批量插入。但是实际情况可能是&#xff0c;项目初期由于种种原因&#xff0c;在业务各处直接使用单条插入SQL进行开发&#xff08;未开启批处理&#xff09;&#xff0c;在后面的迭代中&#xff0c;系统性能问题渐…...

在react项目中如何引入国际化

react-i18next 在 React 项目中引入国际化&#xff08;Internationalization&#xff0c;简称 i18n&#xff09;可以使用第三方库来实现。其中&#xff0c;最常用且流行的国际化库是 react-i18next&#xff0c;它基于 i18next 实现&#xff0c;提供了方便易用的国际化功能。下…...

spring学习笔记十三

注解实现管理第三方Bean和为第三方Bean注入资源 1、添加pom坐标 <dependency><groupId>com.alibaba</groupId><artifactId>druid</artifactId><version>1.1.16</version></dependency> 2、SpringConfig配置类 Configuratio…...

react native 本地存储 AsyncStorage

An asynchronous, unencrypted, persistent, key-value storage system for React Native. Async Storage 只能用来储存字符串数据&#xff0c;所以为了去储存object类型的数据&#xff0c;得先进行序列化&#xff08;JSON.stringify()&#xff09;当你想要使用数据的时候&…...

Postgresql数据库中的时间类型汇总

PostgreSQL数据库有以下几种时间类型 1 日期 date&#xff1a;表示日期&#xff0c;格式为YYYY-MM-DD。 2 时间 time&#xff1a;表示时间&#xff0c;格式为HH:MI:SS。 3 日期和时间 timestamp&#xff1a;表示日期和时间&#xff0c;格式为YYYY-MM-DD HH:MI:SS。 4 带…...

算法刷题Day 51 最佳买卖股票时机含冷冻期+买卖股票的最佳时期含手续费

Day 51 动态规划 309. 最佳买卖股票时机含冷冻期 关键是要画出状态转移图 然后根据状态转移图来写状态转移方程 class Solution { public:int maxProfit(vector<int>& prices) {int len prices.size();vector<vector<int>> dp(len, vector<int&g…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

沙箱虚拟化技术虚拟机容器之间的关系详解

问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西&#xff0c;但是如果把三者放在一起&#xff0c;它们之间到底什么关系&#xff1f;又有什么联系呢&#xff1f;我不是很明白&#xff01;&#xff01;&#xff01; 就比如说&#xff1a; 沙箱&#…...

第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)

第一篇&#xff1a;Liunx环境下搭建PaddlePaddle 3.0基础环境&#xff08;Liunx Centos8.5安装Python3.10pip3.10&#xff09; 一&#xff1a;前言二&#xff1a;安装编译依赖二&#xff1a;安装Python3.10三&#xff1a;安装PIP3.10四&#xff1a;安装Paddlepaddle基础框架4.1…...

jdbc查询mysql数据库时,出现id顺序错误的情况

我在repository中的查询语句如下所示&#xff0c;即传入一个List<intager>的数据&#xff0c;返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致&#xff0c;会导致返回的id是从小到大排列的&#xff0c;但我不希望这样。 Query("SELECT NEW com…...

二维数组 行列混淆区分 js

二维数组定义 行 row&#xff1a;是“横着的一整行” 列 column&#xff1a;是“竖着的一整列” 在 JavaScript 里访问二维数组 grid[i][j] 表示 第i行第j列的元素 let grid [[1, 2, 3], // 第0行[4, 5, 6], // 第1行[7, 8, 9] // 第2行 ];// grid[i][j] 表示 第i行第j列的…...