【数学】【记忆化搜索】【动态规划】964. 表示数字的最少运算符

作者推荐

【动态规划】【字符串】【表达式】2019. 解出数学表达式的学生分数

本文涉及知识点

动态规划汇总

数学记忆化搜索

LeetCoce964表示数字的最少运算符

给定一个正整数 x，我们将会写出一个形如 x (op1) x (op2) x (op3) x … 的表达式，其中每个运算符 op1，op2，… 可以是加、减、乘、除（+，-，*，或是 /）之一。例如，对于 x = 3，我们可以写出表达式 3 * 3 / 3 + 3 – 3，该式的值为 3 。

在写这样的表达式时，我们需要遵守下面的惯例：

除运算符（/）返回有理数。

任何地方都没有括号。

我们使用通常的操作顺序：乘法和除法发生在加法和减法之前。

不允许使用一元否定运算符（-）。例如，“x – x” 是一个有效的表达式，因为它只使用减法，但是 “-x + x” 不是，因为它使用了否定运算符。

我们希望编写一个能使表达式等于给定的目标值 target 且运算符最少的表达式。返回所用运算符的最少数量。

示例 1：

输入：x = 3, target = 19

输出：5

解释：3 * 3 + 3 * 3 + 3 / 3 。表达式包含 5 个运算符。

示例 2：

输入：x = 5, target = 501

输出：8

解释：5 * 5 * 5 * 5 – 5 * 5 * 5 + 5 / 5 。表达式包含 8 个运算符。

示例 3：

输入：x = 100, target = 100000000

输出：3

解释：100 * 100 * 100 * 100 。表达式包含 3 个运算符。

提示：

2 <= x <= 100

1 <= target <= 2 * 10⁸

分析

原理

表达式由若干个xⁿ加减而成,n的范围[0,…)。具有如下性质：

一，对于任意n，不会同时存在加xⁿ，同时减Xⁿ。否则，将两者删除，运算符更少。

二，不会存在x个xⁿ

a,不会存在x个x⁰，否则合并成x。运算符由2x-1，变成0。

b，n>0，不会存在x个xⁿ，否则合并成xⁿ⁺¹运算符由n x-1降成n。

三，n一定大于等0。由于结果是整数，所有小数部分的和一定是整数。假定负数部分是x^-i1 x^-i2… x^-im 。 i1到im升序。如果

∑

i

:

i

1

j

\sum\Large_{i:i1}^{j}

∑i:i1j(xⁱ) < 1，则

∑

i

:

i

1

j

+

1

\sum\Large_{i:i1}^{j+1}

∑i:i1j+1(xⁱ)要么小于1，要么等于1。1 –

∑

i

:

i

1

j

\sum\Large_{i:i1}^{j}

∑i:i1j(xⁱ) = ya^j

y >=1，且a^j >= a^j+1。只有y == 1 j== j+1 时，

∑

\sum\Large_{i:i1}^{j+1}

∑i:i1j+1(xⁱ)为1,其它情况下，其和小于1。为1的小数部分用1替换，运算符更少。

五，类似性质四，xⁱ¹ +xⁱ²… x^im 如果大于等于xⁱⁿ，且i1 i2 …im都小于in，则一定能找到若干项，其和为xⁱⁿ。

六，n>0,xⁿ不劣于 x个x^n-1。

a，表示x，1个x需要0个运算符 x/x + x/x…x/x ，需要2x-1个运算符。

b,n >=2 前者需要 n-1个运算符，后者需要(n-1)*x-1 由于x大于等于2，所以后者大于等于 2n-3 ，由于n>=2，后者大于等于n+2-3=n-1。即后者大于等于前者。

七，xⁿ不劣于xⁱ¹ +xⁱ²… x^im 。根据性质六，用x个X^n-1代替Xⁿ，会变长或不变。用x^n-2代替x^n-1 用x^n-3代替x^n-2 …也是。xⁿ的某个表达式如果有减法，则更长。加的项的和大于xⁿ，根据性质五六替换后更长。

八，根据性质七，t是xⁿ，最少运算符就是xⁿ。下面讨论 t不是x的幂。令a^m-1< t < a^m。则t的表达式不包括a^m+1及更高次方。y = a^m+1-t > a^m+1-a^m 通过性质四，y必定存在(x-1)个a^m 。a^m+1减(x-1)个a^m ，直接用a^m代替运算符更少。

九，t的表达式至少一个表达式是加，不可能全部是减，否则其值是负数。

动态规划

动态规划的状态表示

m_mDp[x]表示 x的最少运算符，如果已经计算不重复计算。

动态规划的转移方程

根据性质八和性质九，枚举j，取值范围[0,m]

{

等于

−

见下面的公式

\begin{cases} 1 & t等于1 \\ m-1 & t = a^m \\ 见下面的公式& else \\ \end{cases}

⎩
⎨
⎧1m−1见下面的公式t等于1t=amelse

{

(

−

)

−

∗

(

[

−

]

)

(

−

)

[

(

−

)

−

]

包括

[

]

[

−

]

根据性质五，只需要考虑

−

min\begin{cases} (a^m-t)/a^{m-1}*(1+dp[a^{m-1}])+(m-1)+dp[(a^m-t) \mod a^{m-1}]+1, & 包括a^m \\ dp[x^j]+1+dp[t-x^n] 根据性质五，只需要考虑j == m-1 & else \\ \end{cases}

min{(am−t)/am−1∗(1+dp[am−1])+(m−1)+dp[(am−t)modam−1]+1,dp[xj]+1+dp[t−xn]根据性质五，只需要考虑j==m−1包括amelse

如果

(

−

)

−

(a^m-t) \mod a^{m-1}

(am−t)modam−1 为0要做特殊处理

[

(

−

)

−

[(a^m-t) \mod a^{m-1}

[(am−t)modam−1

−

a^{m-1}

am−1 x^j t-x^n 全部在[1,t)范围中，所以可以保证收敛性，不断变小。

动态规划的填表顺序

从x向前推。

动态规划的初始值

{

[

]

[

]

−

取

[

)

\begin{cases} dp[1]= 1 & \\ dp[1 << j] = j-1 & j取[0,m)\\ \end{cases}

{dp[1]=1dp[1<<j]=j−1j取[0,m)

动态规划的返回值

dp[target]

代码

核心代码

class Solution {
public:
	int leastOpsExpressTarget(int x, int target) {
		m_x = x;
		m_mDp[1] = 1;
		int i = 0;
		for (long long y = x ; y <= target;y*=x,i++ )
		{
			m_mDp[(int)y] = i;
		}
		return Rec( target);
	}
	int Rec( const int target)
	{
		assert(target > 0);
		if (m_mDp.count(target))
		{
			return m_mDp[target];
		}
	
		long long y = 1;
		int m = 0;
		for (; y <= target; y *= m_x, m++);		
		const long long llSub = y - target;		
		const int am1 = (y / m_x);
		int iRet = Rec(am1) + 1 + Rec(target - am1);
		assert(am1  0 )
		{
			iCur += (1 + Rec(am1)) * iCnt;
		}
		if (llSub % am1 > 0)
		{
			iCur += Rec(llSub % am1) + 1;
		}
		iRet = min(iRet, iCur);
		return m_mDp[target]= iRet;
	}
	unordered_map m_mDp;
	int m_x;

};

测试用例

template
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template
void Assert(const vector& v1, const vector& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{	
	int x,  target;

	{
		Solution sln;
		x = 3, target = 1;
		auto res = sln.leastOpsExpressTarget(x, target);
		Assert(res, 1);
	}
	{
		Solution sln;
		x = 3, target = 3;
		auto res = sln.leastOpsExpressTarget(x, target);
		Assert(res, 0);
	}
	{
		Solution sln;
		x = 3, target = 9;
		auto res = sln.leastOpsExpressTarget(x, target);
		Assert(res, 1);
	}
	{
		Solution sln;
		x = 3, target = 19;
		auto res = sln.leastOpsExpressTarget(x, target);
		Assert(res, 5);
	}

	{
		Solution sln;
		x = 5, target = 501;
		auto res = sln.leastOpsExpressTarget(x, target);
		Assert(res, 8);
	}

	{
		Solution sln;
		x = 100, target = 100000000;
		auto res = sln.leastOpsExpressTarget(x, target);
		Assert(res, 3);
	}
	{
		Solution sln;
		x = 79, target = 155800339;
		auto res = sln.leastOpsExpressTarget(x, target);
		Assert(res, 45);
	}		
	
}

2023年1月版

class Solution {

public:

int leastOpsExpressTarget(int x, int target) {

if (m_mTargetNum.count(target))

{

return m_mTargetNum[target];

}

if (x == target)

{

return m_mTargetNum[target] = 0;

}

if (x > target)

{

//target个1相加和 x不断减1

return m_mTargetNum[target] = min(target + target – 1, 1 + (x – target) * 2 – 1);

}

long long llX = x;

int iMulNum = 0;

while (llX < target)

{

iMulNum++;

llX *= x;

}

int iRet = leastOpsExpressTarget(x,target – llX / x) + 1 + iMulNum – 1;

if (llX – target < target)

{

iRet = min(iRet, leastOpsExpressTarget(x, llX – target) + 1 + iMulNum);

}

return m_mTargetNum[target] = iRet;

}

std::unordered_map m_mTargetNum;

};

2023年7月版

class Solution {

public:

int leastOpsExpressTarget(const int x, const int target) {

if (0 == target)

{

return 0;

}

if (x == target)

{

return 0;

}

if (mValueToOpeNum.count(target))

{

return mValueToOpeNum[target];

}

if (target < x)

{

return mValueToOpeNum[target] = min(2 * target – 1, 2 * (x – target));

}

long long tmp = 1;

int iMulNum = 0;

while (tmp < target)

{

iMulNum++;

tmp *= x;

};

if (target == tmp)

{

return iMulNum – 1;

}

int iRet = (iMulNum – 1)-1 + 1 + leastOpsExpressTarget(x, target – (tmp / x));

if (tmp – target < target)

{

iRet = min(iRet, (iMulNum-1) + 1 + leastOpsExpressTarget(x, tmp – target));

}

return mValueToOpeNum[target] = iRet;

}

std::unordered_map mValueToOpeNum;

};

2023年8月版

class Solution {

public:

int leastOpsExpressTarget(int x, int target) {

while (m_iiMax < target)

{

m_iiMax *= x;

}

return Rec(x, target) – 1;

}

int Rec(int x, int llTarget)

{

if (llTarget > m_iiMax)

{

return 10000;

}

if (0 == llTarget)

{

return 0;

}

if (m_mValueToNum.count(llTarget))

{

return m_mValueToNum[llTarget];

}

int iMulNum = 1;

long long iiMul = x;

while (0 == llTarget % iiMul)

{

iiMul *= x;

iMulNum++;

}

long long llMod = llTarget % iiMul;

const int iOneModNeed = 1 == iMulNum ? 2 : (iMulNum – 1);

const int iModValue = llMod / (iiMul / x);

const int iMay1 = Rec(x, llTarget – llMod) + iOneModNeed * iModValue;

if (llMod == llTarget)

{

const int iMay2 = iMulNum + iOneModNeed * (x – iModValue);

return m_mValueToNum[llTarget] = min(iMay1, iMay2);

}

const int iMay2 = Rec(x, llTarget – llMod + iiMul) + iOneModNeed * (x – iModValue);

return m_mValueToNum[llTarget] = min(iMay1, iMay2);

}

unordered_map m_mValueToNum;

long long m_iiMax=1;

};

【数学】【记忆化搜索】【动态规划】964. 表示数字的最少运算符

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛