- 当前位置：首页 >人工智能 >聊聊笔试必刷的动态规划进阶题
聊聊笔试必刷的动态规划进阶题
发布时间：2025-11-05 12:09:25 来源：云智核 作者：数据库
本文转载自微信公众号「Java极客技术」，聊聊作者鸭血粉丝 。笔试必刷转载本文请联系Java极客技术公众号。态规
Hello 大家好，划进我是阶题阿粉，前面有篇文章给大家介绍了动态规划，聊聊并通过两个案例给大家演示，笔试必刷后台很多小伙伴也提供了很多建议，态规没看过的划进小伙伴可以去看下什么是动态规划——从青蛙跳台阶开始了解。今天再给大家介绍两个案例，阶题帮助大家更好的聊聊掌握也顺便回顾一下。
案例 1
问：给定一个包含非负整数的笔试必刷 m x n 网格，请找出一条从左上角到右下角的态规路径，使得路径上的划进数字总和为最小，其中 arr[m][n] 表示具体的阶题值。每次只能向下或者向右移动一步。这个问题是上篇文章中的案例的进阶篇。
思考
根据上篇文章提供的思路，我们依次进行相关的步骤：
定义变量：我们定义从左上角走到(i, j) 这个位置时，最小的路径和是b2b信息网 dp[i - ][j - 1]。那么，dp[m-1] [n-1] 就是我们要的答案; 寻找关系：dp[i][j] = min(dp[i-1][j]，dp[i][j-1]) + arr[i][j]; arr[i][j] 表示网格中的数值，到达当前格子的最小路径等于左边或者上边中较小的路径加上格子本身的数值; 定义初始值：dp[i][0] = dp[i-1][0] + arr[i][0];，dp[0][i] = dp[0][i-1] + arr[0][i];;第一行或者第一列的时候就是整行和整列的数值累加。编码
上面的分析可以想到，那么接下来我们就需要用代码来实现了，对于需要使用到之前的记录，我们可以考虑用二维数组来记录，所以就有了下面的这段代码。
public int dp(int[][] arr) { int m = arr.length; int n = arr[0].length; if (m <=0 || n <= 0) { return 0; } int[][] dp = new int[m][n]; // 初始化 dp[0][0] = arr[0][0]; // 初始化最左边的列 for(int i = 1; i < m; i++){ dp[i][0] = dp[i-1][0] + arr[i][0]; } // 初始化最上边的行 for(int i = 1; i < n; i++){ dp[0][i] = dp[0][i-1] + arr[0][i]; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = Math.min(dp[i-1][j]，dp[i][j-1]) + arr[i][j]; } } return dp[m - 1][n - 1]; }解释下上面的代码，首先我们创建了一个二维数组 dp[m][n]，用于记录到达位置的最短路径，由于当前的路径是网站模板由左边或者上边的最小路径加上当前格子的数值得到。这里我们需要找到对应关系，也就是dp[i][j] = min(dp[i-1][j]，dp[i][j-1]) + arr[i][j]，这里我们需要取相邻的最小值再加上当前格子的数值。
案例 2
问：给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。Leetcode 322. 零钱兑换。
思考
定义变量：定义 dp[i] 表示凑成金额i，所需要的最少硬币个数，即 dp[amount] 则是我们需要求解的; 寻找关系：假设我们有三种硬币a，b，c，兑换的金币数为 m，我们可以推出 dp[m] = min(dp[m - a], dp[m - b], dp[m - c]) + 1，源码库因为如果我们是需要求 m 金额的最少硬币个数，如果我们求出了 m - a 金额需要的硬币个数，在加上一个 a 就可以得到 m，硬币个数只要加 1。其实b，c 同理。并且我们需要取所有硬币种类的最小数。 定义初始值：dp[0] = 0，没有金额当时也不需要硬币个数，dp[i - coins[j] 需要有解;编码
public int dp(int[] coins, int amount) { int[] dp = new int[amount + 1]; int size = coins.length; int i = 0; int j = 0; # 定义初始值 dp[0] = 0; for (i = 1; i <= amount; i++) { #赋值，当不能组合和输出 -1 判断使用 dp[i] = Integer.MAX_VALUE; # 遍历 coins 中的硬币种类 for (j = 0; j < size; j++) { if (i >= coins[j] && (dp[i - coins[j]]) != Integer.MAX_VALUE) { dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i]); } } } if (dp[amount] == Integer.MAX_VALUE) { dp[amount] = -1 ; } return dp[amount]; }总结
动规划的题目在 LeetCode 上面有很多，大家可以根据上面提供的思路去多刷几道题，慢慢就会有感觉了，刷完动态规划的题目，相信对大家工作或者找工作肯定有很大的帮助。https://leetcode-cn.com/problemset/all/?topicSlugs=dynamic-programming
- 上一篇：关于iptables有价值的信息很多，但是大多都描述的很复杂。假如你想做些基本的配置，下面的 How To 很适合你。 # iptables -L 列出您当前iptables中在规则。假如您是刚刚建立您的服务器，那么可能此时还没有任何规则，而且您应该看到如下： Chain INPUT (policy ACCEPT) Chain FORWARD (policy ACCEPT) Chain OUTPUT (policy ACCEPT) ◆ 允许建立会话 我们可以允许建立会话来接受流量： # iptables -A INPUT -m state --state ESTABLISHED,RELATED -j ACCEPT ◆ 在指定端口上允许入站流量 阻断所有流量您也可以启动系统，但是您可能正在通过SSH工作，所有在您阻断其他流量前有必要允许SSH流量。 为了在22端口号(默认的SSH端口)上的允许流量入站，您可以告诉iptables允许您的网卡接受所有的目的端口为22的TCP流量。 # iptables -A INPUT -p tcp -I eth0 --dport ssh -j ACCEPT 特别的，这将向表中追加(-A)INPUT规则，允许目的端口号为SSH的所有流量进入接口(-i) eth0，以便iptables完成跳转(-j)或动作：ACCEPT 让我们核对下这些规则：(这里仅显示了少数行，您应该看到更多) # iptables -L 现在，让我们允许所有的web流量 # iptables -A INPUT -p tcp -I eth0 --dport 80 -j ACCEPT 检查我们现有的规则 # iptables -L 我们已经指定SSH和web端口为允许通过的TCP流量，但是因为我们还没阻断任何流量，所以到目前为止所有的流量仍然可以进入。 ◆ 阻断流量 一旦一条规则对一个包进行了匹配，其他规则不再对这个包有效。因为我们的规则首先允许SSH和WEB流量，所以只要我们阻断所有流量的规则紧跟其後，我们依然能接受我们感兴趣的流量。大家要做的仅仅是把阻断所有流量的规则放在最後，所以我们需要再次用到它。 # iptables -A INPUT -j DROP 因为我们刚才没有指定一个接口或一个协议，所以除了web和ssh流量外其他任何流量都会被阻断。 ◆ 编辑 iptables 到目前为止我们设置过程中唯一的问题是回环端口(loopbakc)也被阻断了。我们本可以通过指定 -I eth0 来仅仅丢弃eth0上的数据包，但我们也可以为回环端口(loopback)添加一条规则。假如我们追加这条规则，这将太晚了----因为所有的流量已经 被丢弃。我们必须插入这条跪着到第4行。 # iptables -I INPUT 4 -I lo -j ACCEPT 最後2行看起来几乎一样，因此我们可以让iptables列的更详细些。 # iptables -L -v ◆ 日志记录 在上面的例子中，所有的流量都不会被记录。假如您愿意在syslog中记录被丢弃的包, 下面将是最快捷的方式: # iptables -I INPUT 5 -m limit --limit 5/min -j LOG --log-prefix iptables denied: --log-level 7 看 提示 段获得更多关于logging的ideas. ◆ 保存 iptables 假如您现在要重新启动机器的话，您的iptables配置将会消失。为了不用每次重新启动时敲入这些命令，您可以保存你的配置，让它在系统启动时自动启动。你可以通过iptables-save 和iptables-restore命令来保存配置。 保存您的防火墙股则到一个文件 # iptables-save >/etc/iptables.up.rules 接着修改 /etc/network/interfaces 脚本自动应用这些规则(末行是添加的) auto eth0 你也可以准备一组规则冰并自动应用它 auto eth0 ◆ 提示 下面的步骤复习了怎样建立你的防火墙规则，并假定它们相对固定(而且对于大多数人来说它们也应该是)。但是假如你要做许多研究工作，你也许想要你的 iptables在你每次重启时保存一次。你可以在 /etc/network/interfaces 里添加像下面的一行: pre-up iptables-restore < /etc/iptables.up.rules post-down iptables-save >/etc/iptables.up.rules 此行将保存规则用于下次启动时使用。 假如你超出了这个指南来编辑iptables，你可能想利用iptables-save和iptables-restore来编辑和测试你的规则。你可以通过使用你喜爱的文本编辑器(此处为gedit)来打开这些规则文件来完成编辑。 # iptables-save >/etc/iptables.test.rules 你会得到一个如下类似的文件(下面是紧接上的例子文件)： # Generated by iptables-save v1.3.1 on Sun Apr 23 06:19:53 2006 注意到这些都是减去iptables命令的iptables语句。随意编辑这些命令、完成後保存它们。然後简单的测试下： # iptables-restore < /etc/iptables.test.rules 测试完毕後，假如你还没添加iptables-save命令 到 /etc/network/interfaces 里面，记得不要丢失了你的更改： # iptables-save >/etc/iptables.up.rules ◆ 更详细的日志 # Generated by iptables-save v1.3.1 on Sun Apr 23 05:32:09 2006 请注意 一个名为 LOGNDROP的链在文件顶部。而且，INPUT链底部标准的DROP被替换成了LOGNDROP，同时添加了协议描述so it makes sense looking at the log。最後我们在LOGNDROP链尾部丢弃了这些流量。下面的行告诉我们发生了什么： * --limit 设置记录相同规则到syslog中的次数 ◆ 禁用防火墙 假如您要临时禁用防火墙，您可以通过下面的命令清空所偶的规则： # iptables -F ◆ 轻松配置通过 GUI 新手可以利用 Firetarter(一个gui工具)---仓库中的可用软件(新立德或apt-get 获得)来配置她或他的iptables规则，而需要命令行知识。请查看指南，尽管…… 配置很简单，但是对于高级用户来说可能远远不能满足。然而它对于大多数的家庭用户来说是足够的…… 。(我)建议您使用firestarter在策略表中将出站配置为 “限制”，而将您需要的连接类型(如用于http的80、https的443，msn chat的1683等等)加入白名单。您也可以通过它查看进出您计算机的活动连接…… 。防火墙会一直保持下去一旦通过向导配置完毕。拨号用户必须在向导中指定它在拨号时自动启动。 firestarter主页： http://www.fs-security.com/ (再次, 仓库源中可用, 不需要编译) 指南: http://www.fs-security.com/docs/tutorial.php 个人笔记：不幸运的是，它没有阻断(或询问用户)特定应用/程序的选项……。因此，我的理解是一旦启用了80端口(例如，用于访问网页)，那么任何程序都可以通过80端口连接任何服务器、做任何它想做的事……
- 下一篇：用U盘安装Win7系统的详细教程（快速、简便的安装Win7系统方法）
- 电脑显示2105错误的原因及解决方法（解析2105错误，轻松解决电脑显示问题）
- SQL Server日期函数之正确获得一个月中的天数小窍门
- 首席信息安全官的10个预测及2021年如何应对不确定性
- 无孔不入：德国冯克媒体遭受了全国性勒索软件的攻击
- 电脑开不了机解决方法大全（快速解决电脑无法启动的常见问题，让你的电脑重新恢复正常使用）
- 网络安全编程：服务控制管理器实例
- MySQL直接备份数据文件中所要执行的SQL 语句
- 实现MySQL 5.0存储过程的编程入门方案
- Ubuntu升级到12.04失败的解决办法1：按关机键，使用tab键重启2：选择previous version 中的升级前的一个版本的recovery模式，然后进行network修复.3:重启，选择ubuntu第一个选项，进去后网络可以用了，然后更新软件ok了。ps:在恢复模式中可以进行很多操作，清理旧内核，释放空间等等。当ubuntu出了问题，可以进入以前的版本或者修复模式。
- SQL Server数据库中选出指定范围行的SQL语句
随便看看
源码下载IT技术网IT资讯网源码库香港云服务器服务器租用企商汇益华科技亿华云益强科技亿华云多维IT资讯益强资讯优选亿华科技IT资讯网科技前瞻编程之道益强编程堂创站工坊全栈开发益强科技亿华智慧云极客码头码力社亿华智造益华科技益强智囊团益华科技益华IT技术论坛益强数据堂益强编程舍技术快报云智核汇智坊思维库益强智未来码上建站亿华互联亿华云计算益强IT技术网极客编程云站无忧运维纵横
- Copyright © 2025 Powered by 聊聊笔试必刷的动态规划进阶题,云智核 滇ICP备2023006006号-28sitemap