当前位置: 首页 > 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…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...