LeetCode 2139 Minimum Moves to Reach Target Score

LeetCode

You are playing a game with integers. You start with the integer 1 and you want to reach the integer target.

In one move, you can either:

Increment the current integer by one (i.e., x = x + 1). Double the current integer (i.e., x = 2 * x).

You can use the increment operation any number of times, however, you can only use the double operation at most maxDoubles times.

Given the two integers target and maxDoubles, return the minimum number of moves needed to reach target starting with 1.

Example 1:

Input: target = 5, maxDoubles = 0
Output: 4
Explanation: Keep incrementing by 1 until you reach target.

Example 2:

Input: target = 19, maxDoubles = 2
Output: 7
Explanation: Initially, x = 1
Increment 3 times so x = 4
Double once so x = 8
Increment once so x = 9
Double again so x = 18
Increment once so x = 19

Example 3:

Input: target = 10, maxDoubles = 4
Output: 4
Explanation:Initially, x = 1
Increment once so x = 2
Double once so x = 4
Increment once so x = 5
Double again so x = 10

Constraints:

1 <= target <= 10<sup>9</sup> 0 <= maxDoubles <= 100

题目大意：

加1或者乘2达到target，乘2有次数限制，求到达target的最小步数

DFS解题思路(推荐)：

由于是最值，一开始用DP，但得到TLE，分析后觉得是因为加法太慢，所以用贪心法，尽量用乘法。此题类似于求幂值。改用DFS。

解题步骤：

N/A

注意事项：

1. 若允许乘法次数为0，直接返回加法次数，而不应再用递归，否则会出现超过系统栈深度

Python代码：

def minMoves(self, target: int, maxDoubles: int) -> int:
	if target == 1:
		return 0
	if maxDoubles == 0:
		return target - 1
	if target % 2 == 0 and maxDoubles > 0:
		return self.minMoves(target // 2, maxDoubles - 1) + 1

	return self.minMoves(target - 1, maxDoubles) + 1

算法分析：

时间复杂度为O(logn)，空间复杂度O(1)

---

DP算法II解题思路：

TLE

Python代码：

# dp[i][j] = dp[i - 1][j], dp[i // 2][j - 1]
def minMoves2(self, target: int, maxDoubles: int) -> int:
	dp = [[0] * (maxDoubles + 1) for _ in range(target + 1)]
	dp[1][0] = 0
	for i in range(2, len(dp)):
		for j in range(len(dp[0])):
			dp[i][j] = dp[i - 1][j] + 1
			if j >= 1 and i % 2 == 0:
				dp[i][j] = min(dp[i][j], dp[i // 2][j - 1] + 1)
	return dp[-1][-1]

算法分析：

时间复杂度为O(n x maxDoubles)，空间复杂度O(n x maxDoubles)