找出 mustafa 一开始必须具备的最小力量，这样他才能穿过 N 个单元格（面试题）
Find the minimum strength mustafa must have in the beginning so that he can cross N cells (Interview question)
这个问题是在一个公司coding round问的，很遗憾我没能解决，我看到这个问题是基于greedy的，但是无法继续下去，谁有解决方案或者算法请分享给我.
问题陈述：
穆斯塔法想穿越地牢。地牢有N个格子，每个格子里有M个怪物。要穿过每个单元格，他必须杀死一个怪物，在杀死怪物时，他失去了与怪物相等的力量并获得了一些信心，这增加了他的力量，然后他进入了下一个单元格。穆斯塔法只有在自己的实力大于等于怪物的实力的情况下，才能击杀怪物。帮他找出一开始他必须要有的最小力量，这样他才能穿过N个格子。
输入格式：
- 前两个整数是
N 和 M。
N X M矩阵，表示每个单元格中杀死怪物所需的能量。N X M矩阵，表示通过击杀相应的怪物获得的信心。
测试用例：
输入：
3 3
3 2 5
8 9 1
4 7 6
1 1 1
1 1 1
1 1 1
输出：
5
这道题可以用动态规划求解吗？
让我们调用 Energy[N][M]) 杀死每个怪物所需的能量，以及 Conf[N][M] 相关的信心。
让我们称Stren[N]通过每个细胞所需的最小能量。
我们需要在每一步都select 好 怪物。问题是，例如，在第一个单元格中，如果不考虑所有下一个单元格，您将无法做出正确的决定。 DP 解决方案或 DFS 解决方案肯定会起作用。但是，复杂度会很高。
使用贪心解的提示是正确的，条件是从末尾开始。
在最后一个单元格中，很容易计算出所需的强度：
Strength[n-1] = min_i Energy[n-1][i]
然后迭代计算下一个强度，从后到上：
Strength[j] = min_i (Energy[j][i], Energy[j][i] - Conf[j][i] + Strength[j+1]) 对于所有 j
最终结果：Strength[0]
复杂度： 线性 O(NM)。不可能做得更好，因为你必须考虑每个怪物。
一些进一步的解释
以相反的顺序执行迭代是一个经典技巧，当您知道起始值时，这里 Strength[N-1]。
重点是递归公式：
Strength[j] = min_i (Energy[j][i], Energy[j][i] - Conf[j][i] + Strength[j+1])
例如，这也是适用于 DP 的公式。它来自哪里？
对于 Cell j，强度 Strength[j] 必须满足两个约束条件。
您需要杀死当前牢房中的一只怪物。所以，如果怪物i被select攻击，实力必须验证
Strength[j][i] >= Energy[j][i]
填满怪物i后，你需要保持足够的体力，让剩余的体力比Strength[j+]高，才能通过下一个格子
Remaining strength = Strength[j][i] - Energy[j][i] + Conf[j][i] >= Strength[j+1]
所以，如果怪物 i 被 selected，根据这个标准，你必须拥有的最低力量是
Strength[j][i] = Energy[j][i] - Conf[j][i] + Strength[j+1]
对每个怪物都有这两个约束 i，然后你可以 select 最好的 通过最小化这两个阈值的最大值。
import java.util.*;
public class MyClass {
public static void main(String args[]) {
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
int M=sc.nextInt();
int[][] Energy= new int[N][M];
for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++){
Energy[i][j]=sc.nextInt();
}
}
int[][] Conf= new int[N][M];
for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++){
Conf[i][j]=sc.nextInt();
}
}
int temp=0;
int[][]Strength= new int[N+1][M+1];
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
Strength[i][j]= Energy[N-1][i];
Strength[i][j]= Energy[j][i] - Conf[j][i] + Strength[j+1][i];
temp=Strength[i][j];
}
}
System.out.println(temp);
}
}
考虑给定的例子：
Energy = 3 2 5
8 9 1
4 7 6
confi = 1 1 1
1 1 1
1 1 1
现在，一开始我们无法确定通过第一排怪物所需的力量。
因此，我们必须从最后一行开始（因为没有更多的行可以通过）。
现在，我们计算最后一行的最小能量（例如上面的 4）
我们可以从倒数第二行获得的最小能量，即通过倒数第二行后剩余的强度应该是 4.
剩余力量=倒数第二行的力量-能量+确定
4 = str of second last row - energy[i] + confi[i]
倒数第二行的 str = min (4 + energy[i] - confi[i])
我们必须考虑最小强度，因为我们必须输出最小强度。
因此，当前行的强度取决于上一行。
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<vector<int>>energy, confi;
energy = {{3, 2, 5}, {8, 9, 1}, {4, 7, 6}};
confi = {{1, 1, 1}, {1, 1, 1}, {1, 1, 1}};
int n = 3; // no. of rows
int m = 3; // no. of columns
int strength = INT_MAX;
// calculate the min energy from the last row
for(int i=0; i<m; i++)
strength = min(strength, energy[n-1][i]);
// start from the last second row
for(int i = n-2; i>=0; i--){
int temp_min = INT_MAX;
for(int j = 0; j<m; j++){
temp_min = min(temp_min, energy[i][j] - confi[i][j] + strength);
}
strength = temp_min;
}
cout<<strength;
return 0;
}
TL;DR
我注意到到目前为止关于这个问题的所有解决方案都没有通过这个测试用例。如果我没记错的话，答案应该是2.
3 3
3 2 5
8 9 1
4 7 6
1 10 1
1 50 1
1 1 1
我想指出，这个问题是LeetCode Dungeon Game的修改版，你可以看看。
不同之处在于，在这个问题中你不必寻找最佳路径，只有一条路径（即 cell_1 到 cell_N）。另外，在这个问题中，一个单元格同时包含怪物和能量（以 confidence 的形式），不像 LeetCode 问题中一些单元格包含怪物而另一些单元格包含能量。
事不宜迟，让我进入解决方案。在解决任何 DP 问题时，我通常喜欢使用 framework explained here （抱歉，它适用于高级 LeetCode 用户），如果您有兴趣，我建议您检查一下。
框架
- 描述一个递归
function 或 array 来回答给定状态的问题。问题是要求“从 cell_1 战斗到 cell_n 所需的 minimum 力量”。因此，我们将使用函数 dp(i) returns the min strength required to fight from cell_i to cell n，或者数组 dp 其中 dp[i] 表示 the min strength required to fight from cell_i to cell n.
这样，dp(0)或dp[0]就代表了问题的解决方案。请注意，recursive function, dp(i) 用于 Top-Down 方法，而 array, dp[i] 用于 Bottom-up 方法，也称为 Tabulation 方法。
注意：解决DP问题没有单一的方法。例如，当与cell_i的jth个怪物战斗时，您可以决定使用dp[i][j]来表示从cell_i到cell_n所需的最小力量。但是，我选择不在 dp 状态定义中包括每个单元格的怪物选择，因为可以通过简单的线性搜索在每个单元格选择最佳怪物。
- 定义一个
recurrence relation来表示状态之间的转换逻辑。以下是描述我们如何从一种状态转移到另一种状态的步骤。
假设我们在cell_i，我们要计算dp(i)。
- 让 next_state = dp[i+1] (next_state >= 0)。这是因为，在 cell_i，要战斗的怪物的最佳选择取决于（或影响）后面单元格的未来选择。
-此外，让min_strength代表在当前单元格中以最佳方式与怪物战斗所需的最小力量（即cell_i）。
我们想要遍历与怪物战斗所需的能量并随着我们的进行min_strength更新。最后，我们将min_strength分配给dp(i)。因此，对于每个 Energy[i][j]（即 j=1,...,m），我们取 steps i through iv.
我。 initial_strength = Energy[i][j]：这是与当前怪物战斗所需的最低能量。
二。 future_strength = next_state - Confidence[i][j] : 让我们用现在的信心去打未来的仗吧。 future_strength表示我们需要多少能量来为未来的战斗做准备。如果现在的信心不够，future_strength就会是正数，代表我们必须要有能量，才能去迎接未来的战斗。但是，如果当前信心足够，future_strength将为0或负数，这意味着只有当前信心足以完成未来的战斗。因此。
future_strength = max(future_strength, 0)
三。 total_strength = future_strength + initial_strength ：这是我们必须拥有的总数 energy/strength 才能完成从当前格子（即 cell_i）到最后的战斗，如果 jth 怪物被打败.
四。 min_strength = min(min_strength, total_strength)：我们需要跟踪所有 j 的最小强度。
v。解决方案是 dp(0) 或 dp[0].
- 我们最不需要的是基本案例，以便我们的递归关系知道何时停止。基本案例通常是从问题描述中的线索中找到的，或者是使用逻辑思维找到的。在这个问题中，每个状态都依赖于它之后的状态（即
dp[i] 依赖于 dp[i+1]）。如果是这样，最后一个单元格（即 cell_n）的状态取决于哪个状态？当然，dp[n] 依赖于不存在的 dp[n+1]。由于状态dp[n+1]不存在，我们可以假设从dp[n+1]开始战斗需要0强度。
因此我们的 Base Case 是 dp[n+1] = 0 或 dp(n+1) = 0.
JAVA
中的代码实现
一个。 TOP-DOWN ,Time complexity: O(N*M), Space Complexity: O(N) （由于递归调用堆栈）。 N = 格数，M = 怪物数。
这种方法通常是大多数 DP 问题中最直观的方法。大多数时候，Memoization 或 caching 用于提高时间复杂度。但是，在这个问题中，只有一条路径，所以memoization是没有必要的。
private static int topDown(int cell, int[][] energy, int[][] confidence){
//BASE CASE
if(cell == energy.length)return 0;
//current state depends on next states
int nextState = topDown(cell +1, energy, confidence);
//variable to hold min energy required from the current cell
int minStrength = Integer.MAX_VALUE;
for(int j = 0; j< energy[cell].length; j++){
//we must have at least energy[cell][j] to fight this monster,
int required = energy[cell][j];
//Use the current confidence towards future fights
int futureStrength = nextState - confidence[cell][j];
//Notice that if futureStrength <=0, it means confidence gained here
//is enough to finish the subsequent fights
futureStrength = Math.max(futureStrength, 0);
//total strength required to from cell i to the end if monster j is chosen
int totalStrength = required + futureStrength;
minStrength = Math.min(minStrength, totalStrength);
}
return minStrength;
}
乙。 自下而上, Time Complexity: O(N*M), Space Complexity: O(1).
请注意，此方法中没有使用额外的 space，这是因为每个状态仅依赖于紧随其后的状态，因此可以使用一个简单的变量来跟踪状态。
private static int bottomUp(int[][] energy, int[][] confidence){
int n = energy.length, m = energy[0].length;
//base case
int nextState = 0;
for(int cell = n-1; cell>=0; cell--){
//variable to hold min energy required from the current cell
int minStrength = Integer.MAX_VALUE;
for(int j = 0; j < energy[cell].length; j++){
//we must have at least energy[cell][j] to fight this monster,
int required = energy[cell][j];
//Use the current confidence towards future fights
int futureStrength = nextState - confidence[cell][j];
//Notice that if futureStrength <=0, it means confidence gained here
//is enough to finish the subsequent fights
futureStrength = Math.max(futureStrength, 0);
//total strength required to fight from cell i to the end if monster j is chosen
int totalStrength = required + futureStrength;
minStrength = Math.min(minStrength, totalStrength);
}
nextState = minStrength;
}
return nextState;
}
最佳 2 DP 解决方案：
int solve(int cur,int val,vector<vector<int> > p,vector<vector<int> > c,map<pair<int,int>,int> &dp) {
int n = c.size();
int m = c[0].size();
if(cur==n) {
return 0;
}
if(dp.find({cur,val})!=dp.end()) {
return dp[{cur,val}];
}
int ans = INT_MAX;
for(int i=0;i<m;i++) {
int need = 0;
if(val-p[cur][i]<0) {
need = abs(val-p[cur][i]);
}
int curans = need + solve(cur+1,need+val-p[cur][i]+c[cur][i],p,c,dp);
ans = min(curans,ans);
}
return dp[{cur,val}] = ans;
}
int hunt(vector<vector<int> > p,vector<vector<int> > c) {
map<pair<int,int>,int> dp;
int ans = solve(0,0,p,c,dp);
if(ans==INT_MAX) {
ans = -1;
}
return ans;
}
这个问题是在一个公司coding round问的，很遗憾我没能解决，我看到这个问题是基于greedy的，但是无法继续下去，谁有解决方案或者算法请分享给我.
问题陈述：
穆斯塔法想穿越地牢。地牢有N个格子，每个格子里有M个怪物。要穿过每个单元格，他必须杀死一个怪物，在杀死怪物时，他失去了与怪物相等的力量并获得了一些信心，这增加了他的力量，然后他进入了下一个单元格。穆斯塔法只有在自己的实力大于等于怪物的实力的情况下，才能击杀怪物。帮他找出一开始他必须要有的最小力量，这样他才能穿过N个格子。
输入格式：
- 前两个整数是
N和M。 N X M矩阵，表示每个单元格中杀死怪物所需的能量。N X M矩阵，表示通过击杀相应的怪物获得的信心。
测试用例：
输入：
3 3
3 2 5
8 9 1
4 7 6
1 1 1
1 1 1
1 1 1
输出：
5
这道题可以用动态规划求解吗？
让我们调用 Energy[N][M]) 杀死每个怪物所需的能量，以及 Conf[N][M] 相关的信心。
让我们称Stren[N]通过每个细胞所需的最小能量。
我们需要在每一步都select 好 怪物。问题是，例如，在第一个单元格中，如果不考虑所有下一个单元格，您将无法做出正确的决定。 DP 解决方案或 DFS 解决方案肯定会起作用。但是，复杂度会很高。
使用贪心解的提示是正确的，条件是从末尾开始。
在最后一个单元格中，很容易计算出所需的强度：
Strength[n-1] = min_i Energy[n-1][i]
然后迭代计算下一个强度，从后到上：
Strength[j] = min_i (Energy[j][i], Energy[j][i] - Conf[j][i] + Strength[j+1]) 对于所有 j
最终结果：Strength[0]
复杂度： 线性 O(NM)。不可能做得更好，因为你必须考虑每个怪物。
一些进一步的解释
以相反的顺序执行迭代是一个经典技巧，当您知道起始值时，这里 Strength[N-1]。
重点是递归公式：
Strength[j] = min_i (Energy[j][i], Energy[j][i] - Conf[j][i] + Strength[j+1])
例如，这也是适用于 DP 的公式。它来自哪里？
对于 Cell j，强度 Strength[j] 必须满足两个约束条件。
您需要杀死当前牢房中的一只怪物。所以，如果怪物
i被select攻击，实力必须验证Strength[j][i] >= Energy[j][i]填满怪物
i后，你需要保持足够的体力，让剩余的体力比Strength[j+]高，才能通过下一个格子Remaining strength = Strength[j][i] - Energy[j][i] + Conf[j][i] >= Strength[j+1]
所以，如果怪物 i 被 selected，根据这个标准，你必须拥有的最低力量是
Strength[j][i] = Energy[j][i] - Conf[j][i] + Strength[j+1]
对每个怪物都有这两个约束 i，然后你可以 select 最好的 通过最小化这两个阈值的最大值。
import java.util.*;
public class MyClass {
public static void main(String args[]) {
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
int M=sc.nextInt();
int[][] Energy= new int[N][M];
for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++){
Energy[i][j]=sc.nextInt();
}
}
int[][] Conf= new int[N][M];
for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++){
Conf[i][j]=sc.nextInt();
}
}
int temp=0;
int[][]Strength= new int[N+1][M+1];
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
Strength[i][j]= Energy[N-1][i];
Strength[i][j]= Energy[j][i] - Conf[j][i] + Strength[j+1][i];
temp=Strength[i][j];
}
}
System.out.println(temp);
}
}
考虑给定的例子：
Energy = 3 2 5
8 9 1
4 7 6
confi = 1 1 1
1 1 1
1 1 1
现在，一开始我们无法确定通过第一排怪物所需的力量。
因此，我们必须从最后一行开始（因为没有更多的行可以通过）。
现在，我们计算最后一行的最小能量（例如上面的 4） 我们可以从倒数第二行获得的最小能量，即通过倒数第二行后剩余的强度应该是 4.
剩余力量=倒数第二行的力量-能量+确定
4 = str of second last row - energy[i] + confi[i]
倒数第二行的 str = min (4 + energy[i] - confi[i])
我们必须考虑最小强度，因为我们必须输出最小强度。
因此，当前行的强度取决于上一行。
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<vector<int>>energy, confi;
energy = {{3, 2, 5}, {8, 9, 1}, {4, 7, 6}};
confi = {{1, 1, 1}, {1, 1, 1}, {1, 1, 1}};
int n = 3; // no. of rows
int m = 3; // no. of columns
int strength = INT_MAX;
// calculate the min energy from the last row
for(int i=0; i<m; i++)
strength = min(strength, energy[n-1][i]);
// start from the last second row
for(int i = n-2; i>=0; i--){
int temp_min = INT_MAX;
for(int j = 0; j<m; j++){
temp_min = min(temp_min, energy[i][j] - confi[i][j] + strength);
}
strength = temp_min;
}
cout<<strength;
return 0;
}
TL;DR
我注意到到目前为止关于这个问题的所有解决方案都没有通过这个测试用例。如果我没记错的话，答案应该是2.
3 3
3 2 5
8 9 1
4 7 6
1 10 1
1 50 1
1 1 1
我想指出，这个问题是LeetCode Dungeon Game的修改版，你可以看看。
不同之处在于，在这个问题中你不必寻找最佳路径，只有一条路径（即 cell_1 到 cell_N）。另外，在这个问题中，一个单元格同时包含怪物和能量（以 confidence 的形式），不像 LeetCode 问题中一些单元格包含怪物而另一些单元格包含能量。
事不宜迟，让我进入解决方案。在解决任何 DP 问题时，我通常喜欢使用 framework explained here （抱歉，它适用于高级 LeetCode 用户），如果您有兴趣，我建议您检查一下。
框架
- 描述一个递归
function或array来回答给定状态的问题。问题是要求“从cell_1战斗到cell_n所需的minimum力量”。因此，我们将使用函数dp(i)returnsthe min strength required to fight from cell_i to cell n，或者数组dp其中dp[i]表示the min strength required to fight from cell_i to cell n.
这样，dp(0)或dp[0]就代表了问题的解决方案。请注意，recursive function, dp(i) 用于 Top-Down 方法，而 array, dp[i] 用于 Bottom-up 方法，也称为 Tabulation 方法。
注意：解决DP问题没有单一的方法。例如，当与cell_i的jth个怪物战斗时，您可以决定使用dp[i][j]来表示从cell_i到cell_n所需的最小力量。但是，我选择不在 dp 状态定义中包括每个单元格的怪物选择，因为可以通过简单的线性搜索在每个单元格选择最佳怪物。
- 定义一个
recurrence relation来表示状态之间的转换逻辑。以下是描述我们如何从一种状态转移到另一种状态的步骤。
假设我们在cell_i，我们要计算dp(i)。
- 让 next_state = dp[i+1] (next_state >= 0)。这是因为，在 cell_i，要战斗的怪物的最佳选择取决于（或影响）后面单元格的未来选择。
-此外，让min_strength代表在当前单元格中以最佳方式与怪物战斗所需的最小力量（即cell_i）。
我们想要遍历与怪物战斗所需的能量并随着我们的进行min_strength更新。最后，我们将min_strength分配给dp(i)。因此，对于每个 Energy[i][j]（即 j=1,...,m），我们取 steps i through iv.
我。 initial_strength = Energy[i][j]：这是与当前怪物战斗所需的最低能量。
二。 future_strength = next_state - Confidence[i][j] : 让我们用现在的信心去打未来的仗吧。 future_strength表示我们需要多少能量来为未来的战斗做准备。如果现在的信心不够，future_strength就会是正数，代表我们必须要有能量，才能去迎接未来的战斗。但是，如果当前信心足够，future_strength将为0或负数，这意味着只有当前信心足以完成未来的战斗。因此。
future_strength = max(future_strength, 0)
三。 total_strength = future_strength + initial_strength ：这是我们必须拥有的总数 energy/strength 才能完成从当前格子（即 cell_i）到最后的战斗，如果 jth 怪物被打败.
四。 min_strength = min(min_strength, total_strength)：我们需要跟踪所有 j 的最小强度。
v。解决方案是 dp(0) 或 dp[0].
- 我们最不需要的是基本案例，以便我们的递归关系知道何时停止。基本案例通常是从问题描述中的线索中找到的，或者是使用逻辑思维找到的。在这个问题中，每个状态都依赖于它之后的状态（即
dp[i]依赖于dp[i+1]）。如果是这样，最后一个单元格（即cell_n）的状态取决于哪个状态？当然，dp[n]依赖于不存在的dp[n+1]。由于状态dp[n+1]不存在，我们可以假设从dp[n+1]开始战斗需要0强度。
因此我们的Base Case是dp[n+1] = 0或dp(n+1) = 0.
JAVA
中的代码实现一个。 TOP-DOWN ,Time complexity: O(N*M), Space Complexity: O(N) （由于递归调用堆栈）。 N = 格数，M = 怪物数。
这种方法通常是大多数 DP 问题中最直观的方法。大多数时候，Memoization 或 caching 用于提高时间复杂度。但是，在这个问题中，只有一条路径，所以memoization是没有必要的。
private static int topDown(int cell, int[][] energy, int[][] confidence){
//BASE CASE
if(cell == energy.length)return 0;
//current state depends on next states
int nextState = topDown(cell +1, energy, confidence);
//variable to hold min energy required from the current cell
int minStrength = Integer.MAX_VALUE;
for(int j = 0; j< energy[cell].length; j++){
//we must have at least energy[cell][j] to fight this monster,
int required = energy[cell][j];
//Use the current confidence towards future fights
int futureStrength = nextState - confidence[cell][j];
//Notice that if futureStrength <=0, it means confidence gained here
//is enough to finish the subsequent fights
futureStrength = Math.max(futureStrength, 0);
//total strength required to from cell i to the end if monster j is chosen
int totalStrength = required + futureStrength;
minStrength = Math.min(minStrength, totalStrength);
}
return minStrength;
}
乙。 自下而上, Time Complexity: O(N*M), Space Complexity: O(1).
请注意，此方法中没有使用额外的 space，这是因为每个状态仅依赖于紧随其后的状态，因此可以使用一个简单的变量来跟踪状态。
private static int bottomUp(int[][] energy, int[][] confidence){
int n = energy.length, m = energy[0].length;
//base case
int nextState = 0;
for(int cell = n-1; cell>=0; cell--){
//variable to hold min energy required from the current cell
int minStrength = Integer.MAX_VALUE;
for(int j = 0; j < energy[cell].length; j++){
//we must have at least energy[cell][j] to fight this monster,
int required = energy[cell][j];
//Use the current confidence towards future fights
int futureStrength = nextState - confidence[cell][j];
//Notice that if futureStrength <=0, it means confidence gained here
//is enough to finish the subsequent fights
futureStrength = Math.max(futureStrength, 0);
//total strength required to fight from cell i to the end if monster j is chosen
int totalStrength = required + futureStrength;
minStrength = Math.min(minStrength, totalStrength);
}
nextState = minStrength;
}
return nextState;
}
最佳 2 DP 解决方案：
int solve(int cur,int val,vector<vector<int> > p,vector<vector<int> > c,map<pair<int,int>,int> &dp) {
int n = c.size();
int m = c[0].size();
if(cur==n) {
return 0;
}
if(dp.find({cur,val})!=dp.end()) {
return dp[{cur,val}];
}
int ans = INT_MAX;
for(int i=0;i<m;i++) {
int need = 0;
if(val-p[cur][i]<0) {
need = abs(val-p[cur][i]);
}
int curans = need + solve(cur+1,need+val-p[cur][i]+c[cur][i],p,c,dp);
ans = min(curans,ans);
}
return dp[{cur,val}] = ans;
}
int hunt(vector<vector<int> > p,vector<vector<int> > c) {
map<pair<int,int>,int> dp;
int ans = solve(0,0,p,c,dp);
if(ans==INT_MAX) {
ans = -1;
}
return ans;
}