记忆化搜索解决DP状态转移方向不好想的问题

  |  

摘要: 最优子结构+重复子问题 -> 动态规划 -> 状态转移方向不明显 -> 改为记忆化搜索

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


记忆化搜索是一种结合了搜索和动态规划的优点的算法。相应地,理解记忆化搜索算法就有搜索(递归)和动态规划两条路线。

(1)有时我们发现待解决的问题呈现出问题的解依赖于同一个问题的更小实例的解这样的特性,与递归的思想吻合。分析好子问题可以直接解决无需递归的情况,以及如何从子问题结果组装成原问题结果,就可以写出递归的算法解决问题了。但有时候会遇到子问题重复计算的情况,时间复杂度一般是指数型,此时可以开一个备忘录数组,记录子问题的解,形成记忆化搜索

(2)有时我们发现待解决的问题除了问题的解依赖于同一个问题的更小实例的解这种递归特性,还进一步地有最优子结构和重复子问题的特性。此时我们就会直接考虑用动态规划解决,设计好状态,再列出状态转移方程就可以写出动态规划算法了。但是会遇到两个问题,一个是动态规划过程要遍历所有状态,而其中可能有一些是推出最终结果过程中始终没有用到的状态,用记忆化搜索就可以排除掉这些没有用到的状态,更进一步用搜索的话还有可能通过剪枝去掉大量无效状态;另一个是状态的设计、状态转移的方向,状态转移方程等动态规划的要素很多时候很难想,但是用搜索就很容易想,在搜索过程中用记忆化的方式把重复子问题做个记录,这就形成了类似于前面的(1)的思考路线。

总结一下,记忆化搜索可以理解为搜索的形式加上动态规划的思想,结合了搜索的容易想、可以避免对结果无影响的无效状态的计算、可能剪枝的好处,以及动态规划的避免重复子问题的好处。

从递归出发形成记忆化搜索的思考路径是:原问题的解依赖子问题的解 -> 先写出递归算法 -> 然后发现有很多重复子问题 -> 增加记忆化形成记忆化搜索算法。

从动态规划出发形成记忆化搜索的思考路径是:原问题呈现出最优子结构和重复子问题的特性 -> 先写出动态规划算法 -> 发现状态转移过程比较难想/有很多无效状态的计算 -> 改为记忆化搜索算法


本文我们给出一些 DP 状态转移方向不明显,可以通过记忆化搜索解决的问题。

在搜索过程中存在重复子问题,但是想自底向上的话却又不知道底在哪里。

有时 DP 状态可以按照拓扑序来转移 — 做拓扑排序过程中顺便算状态。


329. 矩阵中的最长递增路径

题解参考:DAG上的DP

913. 猫和老鼠

题解参考:【搜索难题】力扣913-染色BFS,minimax

964. 表示数字的最少运算符

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

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

  • 除运算符(/)返回有理数。
  • 任何地方都没有括号。
  • 我们使用通常的操作顺序:乘法和除法发生在加法和减法之前。
  • 不允许使用一元否定运算符(-)。例如,“x - x” 是一个有效的表达式,因为它只使用减法,但是 “-x + x” 不是,因为它使用了否定运算符。

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

提示:

1
2
2 <= x <= 100
1 <= target <= 2 * 1e8

示例 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 个运算符。

算法:动态规划

1
2
3
4
5
6
7
8
9
10
11
状态定义:
dp[t] := 生成 t 的最小代价(含第一个x前的+-)

答案:
dp[t] - 1

状态转移:
dp0 = cost[i] + dp[t - x^i]
dp1 = cost[i + 1] + dp[x^(i+1) - t] 当 x^(i+1) - t < t 是才考虑这项
dp[t] = min(dp0, dp1)
其中 cost[i] := x^i 连同前面的 +- 的运算符个数

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
int leastOpsExpressTarget(int x, int target) {
int n = log2(target) / log2(x);
vector<int> cost(n + 2, 0);
// cost[i] := x^i 连同前面的 +- 的运算符个数
cost[0] = 2;
for(int i = 1; i <= n + 1; ++i)
cost[i] = i;
unordered_map<int, int> dp;
return solve(target, x, cost, dp) - 1;
}

private:
int solve(int t, const int x, const vector<int>& cost, unordered_map<int, int>& dp)
{
// if(dp.count(t) > 0)
// return dp[t];

int i = log2(t) / log2(x);
if(pow(x, i) == t)
return dp[t] = cost[i];

int dp0 = cost[i] + solve(t - pow(x, i), x, cost, dp);
dp[t] = dp0;
if(pow(x, i + 1) - t < t)
{
int dp1 = cost[i + 1] + solve(pow(x, i + 1) - t, x, cost, dp);
dp[t] = min(dp0, dp1);
}
return dp[t];
}
};

818. 赛车

你的赛车可以从位置 0 开始,并且速度为 +1 ,在一条无限长的数轴上行驶。赛车也可以向负方向行驶。赛车可以按照由加速指令 ‘A’ 和倒车指令 ‘R’ 组成的指令序列自动行驶。

  • 当收到指令 ‘A’ 时,赛车这样行驶:
    • position += speed
    • speed *= 2
  • 当收到指令 ‘R’ 时,赛车这样行驶:
    • 如果速度为正数,那么speed = -1
    • 否则 speed = 1

当前所处位置不变。

例如,在执行指令 “AAR” 后,赛车位置变化为 0 —> 1 —> 3 —> 3 ,速度变化为 1 —> 2 —> 4 —> -1 。

给你一个目标位置 target ,返回能到达目标位置的最短指令序列的长度。

提示:

1
1 <= target <= 1e4

示例 1:
输入:target = 3
输出:2
解释:
最短指令序列是 “AA” 。
位置变化 0 —> 1 —> 3 。

示例 2:
输入:target = 6
输出:5
解释:
最短指令序列是 “AAARA” 。
位置变化 0 —> 1 —> 3 —> 7 —> 7 —> 6 。

算法:动态规划

状态定义 $dp[i]$ 表示前进 $i$ 的最少指令数。这样我们的目标是 dp[target]。边界值为 dp[1] = 1, dp[2] = 4

但是状态转移方程非常难想,而如果用记忆化搜索,思路就比较好整理,见代码。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
int racecar(int target) {
for(int i = 1; pow(2, i - 1) <= 10000; ++i)
mapping[pow(2, i) - 1] = i;
int N = (--mapping.end()) -> first;
vector<int> dp(N + 1, -1);
dp[1] = 1;
dp[2] = 4;
return solve(target, dp);
}

private:
map<int, int> mapping;

int solve(int target, vector<int>& dp)
{
if(dp[target] != -1)
return dp[target];

int power = get_k(target);
int k = mapping[power];
if(target == power)
{
dp[target] = solve((target - 1) / 2, dp) + 1;
return dp[target];
}
// 2^(k-1)-1 i < power(2^k-1)
int prev_power = pow(2, k - 1) - 1;
int prev_prev_power = pow(2, k - 2) - 1;
dp[target] = solve(power, dp) + 1 + solve(power - target, dp);
int item = solve(prev_power, dp) + 1;
dp[target] = min(dp[target], item + 1 + solve(target - prev_power, dp));
int i = 0;
while(true)
{
int x = prev_power - (pow(2, i) - 1);
if(x <= prev_prev_power)
break;
int tmp = solve(prev_power - x, dp) + 1;
tmp += solve(target - x, dp);
dp[target] = min(dp[target], item + tmp);
++i;
}

return dp[target];
}

int get_k(int i)
{
// pow(2, k) - 1 >= i 的最小的 k
// pow(2, k - 1) < i <= pow(2, k)
auto it = mapping.lower_bound(i);
return it -> first;;
}
};

1575. 统计所有可行路径

给你一个 互不相同 的整数数组,其中 locations[i] 表示第 i 个城市的位置。同时给你 start,finish 和 fuel 分别表示出发城市、目的地城市和你初始拥有的汽油总量

每一步中,如果你在城市 i ,你可以选择任意一个城市 j ,满足 j != i0 <= j < locations.length ,并移动到城市 j 。从城市 i 移动到 j 消耗的汽油量为 |locations[i] - locations[j]|,|x| 表示 x 的绝对值。

请注意, fuel 任何时刻都 不能 为负,且你 可以 经过任意城市超过一次(包括 start 和 finish )。

请你返回从 start 到 finish 所有可能路径的数目。

由于答案可能很大, 请将它对 1e9 + 7 取余后返回。

提示:

1
2
3
4
5
2 <= locations.length <= 100
1 <= locations[i] <= 1e9
所有 locations 中的整数 互不相同 。
0 <= start, finish < locations.length
1 <= fuel <= 200

示例 1:
输入:locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
输出:4
解释:以下为所有可能路径,每一条都用了 5 单位的汽油:
1 -> 3
1 -> 2 -> 3
1 -> 4 -> 3
1 -> 4 -> 2 -> 3

示例 2:
输入:locations = [4,3,1], start = 1, finish = 0, fuel = 6
输出:5
解释:以下为所有可能的路径:
1 -> 0,使用汽油量为 fuel = 1
1 -> 2 -> 0,使用汽油量为 fuel = 5
1 -> 2 -> 1 -> 0,使用汽油量为 fuel = 5
1 -> 0 -> 1 -> 0,使用汽油量为 fuel = 3
1 -> 0 -> 1 -> 0 -> 1 -> 0,使用汽油量为 fuel = 5

示例 3:
输入:locations = [5,2,1], start = 0, finish = 2, fuel = 3
输出:0
解释:没有办法只用 3 单位的汽油从 0 到达 2 。因为最短路径需要 4 单位的汽油。

算法:动态规划

状态定义 $dp[i][k]$ 表示起点在 $i$,油量为 $k$ 的答案。这样我们的目标是 dp[start][fuel]

边界值和状态转移方程比较难想。如果用记忆化搜索,思路会更清晰一些,见代码。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
public:
int countRoutes(vector<int>& locations, int start, int finish, int fuel) {
int n = locations.size();
dp = vector<vector<int>>(n, vector<int>(fuel + 1, -1));
return solve(locations, start, finish, fuel);
}

private:
vector<vector<int>> dp;
const int MOD = 1e9 + 7;
using ll = long long;

int solve(const vector<int>& locations, int i, const int t, int k)
{
if(k < 0)
return 0;
if(dp[i][k] != -1)
return dp[i][k];
int n = locations.size();
int ans = 0;
if(i == t)
++ans;
for(int j = 0; j < n; ++j)
{
if(i == j)
continue;
ans = ((ll)ans + solve(locations, j, t, k - abs(locations[i] - locations[j]))) % MOD;
}
return dp[i][k] = ans;
}
};

Share