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.tw/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 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習