动态规划是一种优化算法技术，通过将特定问题分解为一些简单的子问题来解决它们。通过这个过程，我们可以将完整搜索的质量、条件或事实结合起来，以获得精确且准确的贪心算法。但这种方法本身就是一个矛盾，因为它有很大的优点，但这也是它最大的缺点和限制。我们可以将一个问题划分为一些子问题，但我们不能再划分子问题。它们应该可以自行解决。子问题的概念可以用来解决更重要的问题，因为它们本质上是高度优化的。
什么是硬币以及如何兑换它？
硬币是表示总金额整数和的数组的组成部分。在这个过程中，您应该返回一些硬币来平衡总和。如果没有构建，则返回-1。
更换硬币有两种解决方案 -
递归 - 单纯且慢的方法。
动态规划 - 一种及时高效的方法
计算机科学中硬币的应用 -
用于分发更改。
硬币操作的算法
以下是我们如何逐步提高相邻行中硬币价值的过程。
第一步 - 开始
第二步 - 构建一个长度为 n+1 的新数组
第 3 步 - 将动态 prog[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]。
Example 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) 并且方向变为左。
Example 2
的翻译为：示例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++构建代码和算法来最大化从相邻行中不能收集的列的硬币的价值。
