动态规划算法
2021/11/6 14:11:01
本文主要是介绍动态规划算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
基本流程
- 找到暴力递归写法(尝试)
- 若有重复解
- 根据可变参数构造缓存
- 不讲究组织,直接进行缓存-》记忆化搜索
- 讲究组织-》经典动态规划
实例
暴力递归改记忆化搜索
int process9(int N, int m, int k, int P, int **dp) { if (dp[m][k] != -1) { return dp[m][k]; } if (k == 0) { if (m == P) { dp[m][k] = 1; return dp[m][k]; } else { dp[m][k] = 0; return dp[m][k]; } } int methods = 0; if (k >= 1) { if (m == 1) { methods += process9(N, m + 1, k - 1, P, dp); } else if (m == N) { methods += process9(N, m - 1, k - 1, P, dp); } else { methods += process9(N, m - 1, k - 1, P, dp); methods += process9(N, m + 1, k - 1, P, dp); } } dp[m][k] = methods; return methods; } int test6(int N, int M, int K, int P) { int** dp = new int* [N + 1]; for (int i = 1; i < N + 1; ++i) { dp[i] = new int[K + 1]; } for (int i = 1; i < N + 1; ++i) { for (int j = 0; j < K + 1; ++j) { dp[i][j] = -1; } } int res = process9(N, M, K, P, dp); for (int i = 1; i < N + 1; ++i) { delete[] dp[i]; } delete[] dp; return res; }
暴力递归改经典动态规划
int test1(const int weights[], const int values[], int bag, int n) { vector<vector<int>> dp(n + 1, vector<int>(bag + 1, 0)); for (int i = n - 1; i >= 0; --i) { for (int j = 0; j <= bag; ++j) { int p1 = -1; int p2 = -1; if (weights[i] <= j) { p1 = values[i] + dp[i + 1][j - weights[i]]; } p2 = dp[i + 1][j]; dp[i][j] = max(p1, p2); } } return dp[0][bag]; }
int test2(const vector<int>& arr) { int n = arr.size(); vector<vector<int>> dp_f(n, vector<int>(n, 0)); vector<vector<int>> dp_s(n, vector<int>(n, 0)); for (int i = 0; i < n; ++i) { dp_f[i][i] = arr[i]; dp_s[i][i] = 0; } for (int i = 1; i < n; ++i) { int l = 0; int r = i; while (r < n && l < n) { dp_f[l][r] = max(arr[l] + dp_s[l + 1][r], arr[r] + dp_s[l][r - 1]); dp_s[l][r] = min(dp_f[l + 1][r], dp_f[l][r - 1]); ++r; ++l; } } return max(dp_f[0][n - 1], dp_s[0][n - 1]); }
这篇关于动态规划算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南