动态规划是一种优化算法技术，通过将特定问题分解为一些简单的子问题来解决它们。通过这个过程，我们可以将完整搜索的质量、条件或事实结合起来，以获得精确且准确的贪心算法。但这种方法本身就是一个矛盾，因为它有很大的优点，但这也是它最大的缺点和限制。我们可以将一个问题划分为一些子问题，但我们不能再划分子问题。它们应该可以自行解决。子问题的概念可以用来解决更重要的问题，因为它们本质上是高度优化的。
什么是硬币以及如何兑换它？
硬币是表示总金额整数和的数组的组成部分。在这个过程中，您应该返回一些硬币来平衡总和。如果没有构建，则返回-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 becollected 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 0If (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
#includeusing namespace std;#define R 5#define C 5bool isValid(int i, int j) { return (i >=0 && i =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 using namespace std;int findMax(vector& arr) { int n = arr.size(), result = 0; vector 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 >& matrix){ int m = matrix.size(); if (m == 0) return 0; vector dp; for (int i = 0; i < m; i++) { int val = findMax(matrix[i]); dp.push_back(val); } return findMax(dp);}int main() { vector<vector > arr = { { 2, 7, 6, 5 }, { 9, 9, 1, 2 }, { 3, 8, 1, 5 } }; int result = solve(arr); cout << result; return 0;}
输出
25
结论
今天在这篇文章中，我们学习了如何通过可能的C++构建代码和算法来最大化从相邻行中不能收集的列的硬币的价值。
以上就是最大化不能收集相邻行和列的硬币的价值的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1445036.html
微信扫一扫 
支付宝扫一扫 
