数据结构
网络
关系型数据库管理系统 (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 次查看
