【数学】【记忆化搜索】【动态规划】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升序。如果 $\sum\Large_{i:i1}^{j}$ (xⁱ) < 1，则 $\sum\Large_{i:i1}^{j+1}$ (xⁱ)要么小于1，要么等于1。1 - $\sum\Large_{i:i1}^{j}$ (xⁱ) = ya^j
y >=1，且a^j >= a^j+1。只有y == 1 j== j+1 时， $\sum\Large_{i:i1}^{j+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}$

$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}$
如果 $a^m-t) \mod a^{m-1}$ 为0要做特殊处理
$a^m-t) \mod a^{m-1}$ $a^{m-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[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 < target);const int iCnt = llSub / am1;int iCur = m - 1;if (iCnt > 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<int,int> m_mDp;int m_x;};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}template<class T>
void Assert(const vector<T>& v1, const vector<T>& 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<int, int> 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<int, int> 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<long long, int> m_mValueToNum;
long long m_iiMax=1;
};

扩展阅读

视频课程

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

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

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