C++程序检查k卢比是否足以到达最终单元格

假设我们有三个数字n、m和k。有一个n x m的网格。我们目前位于左上角的单元格(0,0)，并且想要到达单元格(n - 1, m - 1)。我们可以移动到右侧或下方的相邻单元格。向下移动需要x卢比，向右移动需要y卢比。我们必须检查我们是否能够花费恰好k卢比到达单元格(n - 1, m - 1)。(x和y分别是单元格的当前x和y坐标+1)

问题类别

给定的问题是分治问题的示例，我们可以使用动态规划来解决。动态规划是一种分治技术，其中特定问题被分解成子问题，然后解决。正常的分治技术和动态规划之间存在差异，即后者解决重叠的子问题并在再次需要时使用该结果。为了存储这些重叠子问题的结果，动态规划技术使用一个表，这个过程称为“记忆化”。每次必须解决子问题时都会检查表中的数据。通常，动态规划技术用于优化问题，其中必须找到解决方案的最优值。此编程技术的示例包括斐波那契数列问题、Bellman-Ford单源最短路径问题、矩阵链乘法问题、最长公共子序列问题等。

https://tutorialspoint.com/data_structures_algorithms/dynamic_programming.htm

因此，如果我们问题的输入类似于n = 2；m = 2；k = 3，则输出将为True。

步骤

为了解决这个问题，我们将遵循以下步骤：

if k is same as n * m - 1, then:
   return true
Otherwise
   return false

示例

让我们看看以下实现以更好地理解：

#include <bits/stdc++.h>
using namespace std;
bool solve(int n, int m, int k){
   if (k == n * m - 1)
      return true;
   else
      return false;
}
int main(){
   int n = 2;
   int m = 2;
   int k = 3;
   cout << solve(n, m, k) << endl;
}

输入

2, 2, 3

输出

1

Arnab Chakraborty

更新于: 2022年4月8日

105 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习