【数学】【记忆化搜索】【动态规划】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 时，∑ i : i 1 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]

{ 1 t 等于 1 m − 1 t = a m 见下面的公式 e l s e \begin{cases} 1 & t等于1 \\ m-1 & t = a^m \\ 见下面的公式& else \\ \end{cases}⎩⎨⎧1m−1见下面的公式t等于1t=amelse

m i n { ( a m − t ) / a m − 1 ∗ ( 1 + d p [ a m − 1 ] ) + ( m − 1 ) + d p [ ( a m − t ) m o d a m − 1 ] + 1 , 包括 a m d p [ x j ] + 1 + d p [ t − x n ] 根据性质五，只需要考虑 j = = m − 1 e l s e 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 ) m o d a m − 1 (a^m-t) \mod a^{m-1}(am−t)modam−1 为0要做特殊处理

[ ( a m − t ) m o d a m − 1 [(a^m-t) \mod a^{m-1}[(am−t)modam−1 a m − 1 a^{m-1}am−1 x^j t-x^n 全部在[1,t)范围中，所以可以保证收敛性，不断变小。

动态规划的填表顺序

从x向前推。

动态规划的初始值

{ d p [ 1 ] = 1 d p [ 1 < < j ] = j − 1 j 取 [ 0 , m ) \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 < 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;

};

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

作者推荐

本文涉及知识点

LeetCoce964表示数字的最少运算符

分析

原理