2023华为od机试统一考试B卷 Java【求最小步数/动态规划】_坐标0点到n的最小步数

作者：小蓝xlanll | 2024-04-19 07:12:01

踩

坐标0点到n的最小步数

前言

本题使用 Java 解答，如果需要 Python 解答，请参考以下：
点我

题目

描述：给定一个整数坐标点n，从坐标点0开始，每次只能沿横轴左右移动2或3个单位，请计算到达坐标点n的最小步骤数。注意，中间经过的坐标点可以为负。

输入：一个整数n (1 <= n <= 10^9)。

输出：一个整数，表示从坐标点0到n所需的最小步数。

示例：

输入：4
输出：2

提示：从坐标点0移动到4可分为两步：首先右移2个单位，然后再右移2个单位。

在这里插入图片描述

解题思路

定义一个数组 dp，其中 dp[i] 表示从坐标零点移动到坐标点 i 的最小步数。
初始状态下，dp[0] = 0，即从坐标零点到自身的最小步数为 0。
然后，我们从 i = 1 开始迭代计算 dp[i] 的值，每次只能沿横坐标轴向左或向右移动 2 或 3。因此，我们可以考虑前一步的状态，即 dp[i-2] 和 dp[i-3]，然后取其中的较小值，并加上 1（表示移动一步）。

</

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/450486