資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究最大化硬幣價值，但相鄰行和列的硬幣不能被收集
動態規劃是一種最佳化演算法技術，用於透過將特定問題分解成一些簡單的子問題來解決這些問題。它是一種可以透過結合完整搜尋的質量、條件或事實來使貪婪演算法精確和準確的過程。但是，這種方法本身就是一個矛盾修辭法，因為它具有很大的優勢，而這同時也是它最大的缺點和侷限性。我們可以將問題分解成一些子問題，但我們不能再次分解子問題。它們應該能夠獨立解決。子問題的概念可用於解決更重要的問題，因為它們本質上是高度最佳化的。
什麼是硬幣以及如何兌換？
硬幣是陣列的組成部分，表示總金額的整數之和。在此過程中，您應該返還一些硬幣以平衡總和。如果無法構造，則返回 -1。
有兩種解決方案可以兌換硬幣：
遞迴 - 樸素且緩慢的方法。
動態規劃 - 及時且高效的方法
硬幣在計算機科學中的應用：
用於分配零錢。
硬幣操作演算法
以下是我們如何最大化相鄰行硬幣價值的分步過程。
步驟 1 - 開始
步驟 2 - 建立一個長度為 n+1 的新陣列
步驟 3 - 將 dynamicprog[0] 設定為 1，用於單向過程
步驟 4 - 迭代值
步驟 5 - 將 dynamicprog[index-coins[i]] 的值新增到 dynamicprog[index]
步驟 6 - 設定從 1 到 n 的範圍
步驟 7 - 返回一個值
步驟 8 - 終止
硬幣語法
If the coin value is greater than the dynamicprogSum, the coin is ignored, i.e. dynamicprogTable[i][j]=dynamicprogTable[i-1][j]. If the coin value is less than the dynamicprogSum, you can consider it, i.e. dynamicprogTable[i][j]=dynamicprogTable[i- 1].[dynamicprogSum]+dynamicprogTable[i][j-coins[i-1]]. Or; maxCoins(i, j, d): Maximum number of coins that can be collected if we begin at cell (i, j) and direction d. d can be either 0 (left) or 1 (right) If (arr[i][j] == ‘#’ or isValid(i, j) == false) return 0 If (arr[i][j] == ‘C’) result = 1; Else result = 0; If (d == 0) return result + max(maxCoins(i+1, j, 1), maxCoins(i, j-1, 0)); If (d == 1) return result + max(maxCoins(i+1, j, 1), maxCoins(i, j+1, 0));
以下是 C++ 環境中硬幣兌換的可能語法。透過應用此語法，我們將構建一些程式碼來全面瞭解此硬幣。
遵循的方法：
方法 1 - 遞迴 C++ 程式，用於查詢最大硬幣數量
方法 2 - 當來自相鄰行和列的硬幣無法收集時，最大化硬幣價值
遞迴 C++ 程式，用於查詢最大硬幣數量
在此程式碼中，我們應用了動態規劃。邏輯是：arr[i][j + 1] 和 arr[i][j – 1]。
示例 1
#include<bits/stdc++.h>
using namespace std;
#define R 5
#define C 5
bool isValid(int i, int j) {
return (i >=0 && i < R && j >=0 && j < C);
}
int maxCoinsRec(char arr[R][C], int i, int j, int dir){
if (isValid(i,j) == false || arr[i][j] == '#')
return 0;
int result = (arr[i][j] == 'C')? 1: 0;
if (dir == 1)
return result + max(maxCoinsRec(arr, i+1, j, 0),
maxCoinsRec(arr, i, j+1, 1));
return result + max(maxCoinsRec(arr, i+1, j, 1),
maxCoinsRec(arr, i, j-1, 0));
}
int main() {
char arr[R][C] = {
{'E', 'C', 'C', 'C', 'C'},
{'C', '#', 'C', '#', 'E'},
{'#', 'C', 'C', '#', 'C'},
{'C', 'E', 'E', 'C', 'E'},
{'C', 'E', '#', 'C', 'E'}
};
cout << "Maximum number of collected coins is "<< maxCoinsRec(arr, 0, 0, 1);
return 0;
}
輸出
Maximum number of collected coins is 8
當來自相鄰行和列的硬幣無法收集時，最大化硬幣價值
在此 C++ 程式碼中，我們應用了該方法來查詢並在到達死衚衕之前收集最大數量的硬幣。
向前移動一步，即單元格 (i, j+1)，方向保持向右。
向下移動一步並向左，即單元格 (i+1, j)，方向變為向左。
示例 2
#include <bits/stdc++.h>
using namespace std;
int findMax(vector<int>& arr) {
int n = arr.size(), result = 0;
vector<int> dp(n);
dp[0] = arr[0];
result = dp[0];
if (n <= 1)
return result;
dp[1] = max(arr[1], arr[0]);
result = max(result, dp[1]);
for (int i = 2; i < n; i++) {
dp[i] = max(dp[i - 1], arr[i] + dp[i - 2]);
result = max(result, dp[i]);
}
return result;
}
int solve(vector<vector<int> >& matrix){
int m = matrix.size();
if (m == 0)
return 0;
vector<int> dp;
for (int i = 0; i < m; i++) {
int val = findMax(matrix[i]);
dp.push_back(val);
}
return findMax(dp);
}
int main() {
vector<vector<int> > arr = { { 2, 7, 6, 5 },
{ 9, 9, 1, 2 },
{ 3, 8, 1, 5 } };
int result = solve(arr);
cout << result;
return 0;
}
輸出
25
結論
今天在這篇文章中，我們學習瞭如何使用可能的 C++ 構建程式碼和演算法，最大化來自相鄰行（列不能被收集）的硬幣價值。
157 次檢視
