C/C++仿高山每周一练2（难度增加）
本帖最后由 陈尚涵 于 2022-10-6 14:42 编辑或许是因为今天没事干吧，竟然做出了两个这样的帖子{:10_257:}
题目：数塔问题
难度：t2-t3（非常经典的一道题目，网上随便一搜就能找到答案，如果只是为了骗鱼币，请立刻退出这个帖子）
题目描述：有如下所示的数塔，要求从底层走到顶层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输入：第一行：一个整数（N），表示数塔高度
第(2-)行：（2-）个整数，表示数塔
输出：经过的结点的最大数字之和
输入样例：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例：
30
注意：此题通过暴力只能拿到1个鱼币，但是使用动态规划能拿到3个鱼币！
本来暴力想设置2个鱼币，但一想，暴力的难度不如每周一练1，所以设置了1个鱼币 #include<iostream>
using namespace std;
int a, n;
int dp(int s, int x, int y) {
if(x == n-1) {
return s + a;
}
return max(dp(s+a, x+1, y), dp(s+a, x+1, y+1));
}
int main()
{
cin>>n;
for(int i=0; i<n; ++i) {
for(int j=0; j<=i; ++j) {
cin>>a;
}
}
cout<<dp(0, 0, 0);
return 0;
} 陈尚涵 发表于 2022-10-6 14:13
本来暴力想设置2个鱼币，但一想，暴力的难度不如每周一练1，所以设置了1个鱼币
啥叫动态规划? 本帖最后由 陈尚涵 于 2022-10-6 14:46 编辑
元豪 发表于 2022-10-6 14:35
啥叫动态规划?
看来你还需要学习算法
动态规划是一种算法的思想
我个人的理解是
每一个下标都对应着一个状态，值就是多种方案的选择，多用于求最佳方案，方案数和背包问题。
使用动态规划可以优化程序的时间复杂度，比如这道题的时间复杂度可以从O(2^n)降低到O(n^2) 陈尚涵 发表于 2022-10-6 14:40
看来你还需要学习算法
动态规划是一种算法的思想
我个人的理解是
那暴力呢? 本帖最后由 陈尚涵 于 2022-10-6 15:02 编辑
元豪 发表于 2022-10-6 14:58
那暴力呢?
这题暴力一般就是递归，非常简单
但是如果是CSP中，暴力是拿不了多少分的 陈尚涵 发表于 2022-10-6 15:01
这题暴力一般就是递归，非常简单
但是如果是CSP中，暴力是拿不了多少分的
简单{:10_266:} 元豪 发表于 2022-10-6 15:06
雀食简单，如果用暴力，最多t2水平。 元豪 发表于 2022-10-6 15:06
雀食简单，暴力最多t2，你还需要学习 也来玩玩
#include <stdio.h>
int main(){
int n;
scanf("%d", &n);
int best;
scanf("%d", best);
int max = 0;
int input, temp;
for(int i = 2; i <= n; ++i){
for(int j = 0; j < i; ++j){
scanf("%d", &input);
if(j == 0){
max = temp = input + best;
}else{
if(j == i - 1){
best = best + input;
}else{
best = (best > best ? best : best) + input;
}
best = temp;
temp = best;
if(temp > max) max = temp;
}
}
}
printf("%d\n", max);
return 0;
} dolly_yos2 发表于 2022-10-6 15:49
也来玩玩
数组的大小是固定的，第5行这个代码有问题
你这么写有点偏暴力了，算暴力吧 本帖最后由 dolly_yos2 于 2022-10-6 16:10 编辑
陈尚涵 发表于 2022-10-6 15:55
数组的大小是固定的，第5行这个代码有问题
你这么写有点偏暴力了，算暴力吧
啊这 第五行 VLA 应该没啥问题（虽然说是一个可选支持的标准特性但是主流的实现应该都支持的）
另外这明显是个 n^2 的动态规划啊，只不过压缩了存储空间（只存一行）（虽然代码变得复杂了起来）
（鱼币 1 个还是 3 个甚至有还是没有我都不在乎，不过事实还是要分析的） 陈尚涵 发表于 2022-10-6 14:40
看来你还需要学习算法
动态规划是一种算法的思想
我个人的理解是
记忆化搜索也是 dp 哦 dolly_yos2 发表于 2022-10-6 16:04
啊这 第五行 VLA 应该没啥问题（虽然说是一个可选支持的标准特性但是主流的实现应该都支持的）
另外这明 ...
对不起哈，我又看了一下，可能因为你把数组命名成best不是dp，而且9-25不像dp的缘故，我以为是暴力，但是dp一般都用max()，你这判断分支有点多啊，我给你补上2鱼币{:10_257:}
数组的数量是固定的，第5行有点小问题啊，一些编译器过不去的
柿子饼同学 发表于 2022-10-6 16:08
记忆化搜索也是 dp 哦
学到了 陈尚涵 发表于 2022-10-6 16:12
对不起哈，我又看了一下，可能因为你把数组命名成best不是dp，而且9-25不像dp的缘故，我以为是暴力，但是 ...
可以了解一下 VLA ，这样写起来能根据实际需要开辟数组空间大小，代码也相当简洁，主流的编译器像是 Clang 和 GCC 都是支持的（当然也不排除很可能有一些编译器是不支持的，毕竟是一个实现可以选择支持或者不支持的特性）
分支主要是要压缩存储空间和处理边界检查问题，如果做一下扩展的话（哨兵位置之类的）应该会简洁一些，不过就又需要额外的存储空间了。也能看出来某种程度上就是时间复杂度、空间复杂度和代码复杂度之间的取舍和制衡。
刚才也说了鱼币我不在乎，还是把这两个鱼币再还给您吧，不然我好像是得了便宜还卖乖 #include <cstdio>
#include <algorithm>
using namespace std;
int main() {
int n;
scanf("%d", &n);
int a, f;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= i; ++j)
scanf("%d", &a);
for (int j = 1; j <= n; ++j)
f = a;
for (int i = n - 1; i >= 1; --i) {
for (int j = 1; j <= i; ++j) {
f = a + max(f, f);
}
}
printf("%d", f);
}
从下往上推....
页:
[1]