复习动态规划入门

题目：

最小花费爬楼梯

暴力：

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
int cost[N];
int dfs(int x)
{if(x == 0 || x == 1)return 0;elsereturn min(dfs(x-1) + cost[x-1],dfs(x-2) + cost[x-2]);
}
int main()
{cin >> n;for(int i = 0 ; i < n ; i++)cin >> cost[i];cout << dfs(n);return 0; 
}

记忆化搜索：

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
int cost[N];
int mem[N];//到达第i层之前最小花费 
int dfs(int x)
{int sum = 0;if(mem[x])return mem[x]; if(x == 0 || x == 1)return 0;elsesum = min(dfs(x-1) + cost[x-1],dfs(x-2) + cost[x-2]);mem[x] = sum;return sum;
}
int main()
{cin >> n;for(int i = 0 ; i < n ; i++)cin >> cost[i];cout << dfs(n);return 0; 
}

dp1：

dp定义到达第i层前最小花费

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
int cost[N];
int f[N];//到达第i层最小花费 
int main()
{cin >> n;for(int i = 0 ; i < n ; i++)cin >> cost[i];f[0] = f[1] = 0;for(int i = 2 ; i <= n ; i++){f[i] = min(f[i-1]+cost[i-1],f[i-2]+cost[i-2]);}//cout << f[n];for(int i = 0 ; i <= n ; i++)cout <<f[i] << " "; return 0; 
}

dp2：

dp定义到达第i层的最小花费

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
int cost[N];
int f[N];//到达第i层最小花费 
int main()
{cin >> n;for(int i = 0 ; i < n ; i++)cin >> cost[i];f[0] = 0;for(int i = 1 ; i <= n ; i++){f[i] = min(f[i-1]+cost[i-1],f[i-2]+cost[i-2]);}cout << f[n];
/*	for(int i = 0 ; i <= n ; i++)cout <<f[i] << " "; */return 0; 
}

最长递增子序列：
B3637 最长上升子序列 - 洛谷 | 计算机科学教育新生态

dfs：

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
int arr[N];
int f[N];
int dfs(int x)
{int sum = 1;for(int i = 1 ; i < x ; i++)//注意是＜ {if(arr[i] < arr[x]){sum = max(sum,dfs(i) + 1);}}return sum;
}
int main()
{int ans = -1;cin >> n;for(int i = 1 ; i <= n ; i++)cin >> arr[i];for(int i = 1 ; i <= n ; i++){ans = max(ans,dfs(i));} cout << ans; return 0; 
}

记忆化搜索：

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
int arr[N];
int mem[N];//存的是以i为结尾最长上升子序列的最大值 
int dfs(int x)
{int sum = 1;if(mem[x])return mem[x]; for(int i = 1 ; i < x ; i++)//注意是＜ {if(arr[i] < arr[x]){sum = max(sum,dfs(i) + 1);}}mem[x] = sum;return sum;
}
int main()
{int ans = -1;cin >> n;for(int i = 1 ; i <= n ; i++)cin >> arr[i];for(int i = 1 ; i <= n ; i++){ans = max(ans,dfs(i));} cout << ans; return 0; 
}

dp：

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
int arr[N];
int f[N];//存的是以i为结尾最长上升子序列的最大值 int main()
{int ans = -1;cin >> n;for(int i = 1 ; i <= n ; i++){cin >> arr[i];f[i] = 1;		}for(int i = 1 ; i <= n ; i++){for(int j = 1 ; j < i ; j++){if(arr[j] < arr[i]){f[i] = max(f[i],f[j] + 1);}}} for(int i = 1 ; i <= n ; i++)ans = max(ans,f[i]);cout << ans; return 0; 
}

零钱兑换

B3635 硬币问题 - 洛谷 | 计算机科学教育新生态

记忆化搜索：

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e6+10;
int n;
int len = 0;
int arr[10] = {1,5,11};
int mem[N];
int dfs(int x)
{int sum = 1e9;if(mem[x])return mem[x];if(x == 0 || x < 0)return 0;for(int i = 0 ; i < 3 ; i++){if(arr[i] <= x){sum = min(sum,dfs(x - arr[i]) + 1);}}mem[x] = sum;return sum;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int x;cin >> n;cout << dfs(n); return 0;
}

dp：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 1e6 + 10;
int n;
int arr[10] = {1, 5, 11};
int f[N];int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for(int i = 1 ; i <= n ; i++)f[i] = 1e9;for (int i = 0; i <= n; ++i) {for (int j = 0; j < 3; ++j){if (i >= arr[j]){f[i] = min(f[i], f[i - arr[j]] + 1);}}}if (f[n] == 1e9) {cout << -1; } else {cout << f[n];}return 0;
}

连续子数组的最大和：

贪心：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
const int N = 1e6+10;
int arr[N];
int main() 
{cin >> n;for(int i = 1 ; i <= n ; i++)cin >> arr[i];int ans = -1e9,sum = 0;for(int i = 1 ; i <= n ; i++){if(sum < 0)sum = 0;sum += arr[i];ans = max(ans,sum);}cout << ans;return 0;
}
/* 
9
-2 1 -3 4 -1 2 1 -5 4
*/

局部最优到全局最优的转换：Kadane's Algorithm通过维护一个当前子数组的最大和（sum）和一个全局最大和（ans），在遍历数组时，如果当前子数组的和变为负数，则重新开始计算新的子数组和（即重置sum为0）。这种方法确保了每一步都是在尝试找到以当前元素为结尾的子数组中的最大和。由于我们总是在更新ans为遇到的最大子数组和，因此当遍历结束时，ans就是全局最大子数组和。
无需回溯：与动态规划等方法不同，Kadane's Algorithm不需要回溯或存储中间状态。它只依赖于当前遍历到的元素和之前的累积和，这使得算法非常高效，时间复杂度为O(n)。
贪心选择的正确性：在这个特定问题中，贪心选择的正确性在于我们总是尝试扩展当前子数组（只要它的和仍然是非负的），或者当遇到一个使当前子数组和变为负数的元素时，我们重新开始一个新的子数组。这种方法确保了我们不会错过任何可能构成全局最大子数组的部分。
问题的特定结构：最大子数组和问题具有一种特殊结构，使得局部最优解（以当前元素为结尾的最大子数组和）能够直接导向全局最优解（整个数组中的最大子数组和）。这种结构是贪心算法能够成功应用的关键。

暴力dfs：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
const int N = 1e6+10;
int arr[N];
int dfs(int x)
{if(x == 0)return 0;int sum = -1e9;sum = max(arr[x],dfs(x - 1) + arr[x]);return sum;
}
int main() 
{int ans = -1e9;cin >> n;for(int i = 1 ; i <= n ; i++)cin >> arr[i];for(int i = 1 ; i <= n ; i++){ans = max(ans,dfs(i));}cout << ans;return 0;
}
/* 
9
-2 1 -3 4 -1 2 1 -5 4
*/

记忆化搜索：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
const int N = 1e6+10;
int arr[N];
int mem[N]; 
int dfs(int x)
{if(mem[x])return mem[x];if(x == 0)return 0;int sum = -1e9;sum = max(arr[x],dfs(x - 1) + arr[x]);mem[x] = sum;return sum;
}
int main() 
{int ans = -1e9;cin >> n;for(int i = 1 ; i <= n ; i++)cin >> arr[i];for(int i = 1 ; i <= n ; i++){ans = max(ans,dfs(i));}cout << ans;return 0;
}
/* 
9
-2 1 -3 4 -1 2 1 -5 4
*/

动态规划：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
const int N = 1e6+10;
int arr[N];
int f[N]; 
/*int dfs(int x)
{if(mem[x])return mem[x];if(x == 0)return 0;int sum = -1e9;sum = max(arr[x],dfs(x - 1) + arr[x]);mem[x] = sum;return sum;
}*/
int main() 
{int ans = -1e9;cin >> n;for(int i = 1 ; i <= n ; i++)cin >> arr[i];for(int i = 1 ; i <= n ; i++){f[i] = max(f[i] , f[i-1] + arr[i]);}for(int i = 1 ; i <= n ; i++){if(ans < f[i])ans = f[i];}cout << ans;return 0;
}
/* 
9
-2 1 -3 4 -1 2 1 -5 4
*/

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/6764.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！