C/C++仿高山每周一练2（难度增加）

陈尚涵

或许是因为今天没事干吧，竟然做出了两个这样的帖子

题目：数塔问题
难度：t2-t3（非常经典的一道题目，网上随便一搜就能找到答案，如果只是为了骗鱼币，请立刻退出这个帖子）
题目描述：有如下所示的数塔，要求从底层走到顶层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？

1.     7
   
2.    3 8
   
3.   8 1 0
   
4. 2 7 4 4
   
5. 4 5 2 6 5

复制代码

输入：第一行：一个整数（N），表示数塔高度
         第(2-[N+1])行：（2-[N+1]）个整数，表示数塔

输出：经过的结点的最大数字之和

输入样例：

1. 5
   
2. 7
   
3. 3 8
   
4. 8 1 0
   
5. 2 7 4 4
   
6. 4 5 2 6 5

复制代码

输出样例：

1. 30

复制代码

注意：此题通过暴力只能拿到1个鱼币，但是使用动态规划能拿到3个鱼币！

陈尚涵

本来暴力想设置2个鱼币，但一想，暴力的难度不如每周一练1，所以设置了1个鱼币

tommyyu

1. #include<iostream>
   
2. using namespace std;
   
3. int a[200][200], n;
   
4. int dp(int s, int x, int y) {
   
5.         if(x == n-1) {
   
6.                 return s + a[x][y];
   
7.         }
   
8.         return max(dp(s+a[x][y], x+1, y), dp(s+a[x][y], x+1, y+1));
   
9. }
   
10. int main()
    
11. {
    
12.         cin>>n;
    
13.         for(int i=0; i<n; ++i) {
    
14.                 for(int j=0; j<=i; ++j) {
    
15.                         cin>>a[i][j];
    
16.                 }
    
17.         }
    
18.         cout<<dp(0, 0, 0);
    
19.         return 0;
    
20. }

复制代码

元豪

陈尚涵 发表于 2022-10-6 14:13
本来暴力想设置2个鱼币，但一想，暴力的难度不如每周一练1，所以设置了1个鱼币

啥叫动态规划?

陈尚涵

元豪 发表于 2022-10-6 14:35
啥叫动态规划?

看来你还需要学习算法
动态规划是一种算法的思想
我个人的理解是
每一个下标都对应着一个状态，值就是多种方案的选择，多用于求最佳方案，方案数和背包问题。
使用动态规划可以优化程序的时间复杂度，比如这道题的时间复杂度可以从O(2^n)降低到O(n^2)

元豪

陈尚涵 发表于 2022-10-6 14:40
看来你还需要学习算法
动态规划是一种算法的思想
我个人的理解是

那暴力呢?

陈尚涵

元豪 发表于 2022-10-6 14:58
那暴力呢?

这题暴力一般就是递归，非常简单
但是如果是CSP中，暴力是拿不了多少分的

元豪

陈尚涵 发表于 2022-10-6 15:01
这题暴力一般就是递归，非常简单
但是如果是CSP中，暴力是拿不了多少分的

简单

陈尚涵

元豪 发表于 2022-10-6 15:06

雀食简单，如果用暴力，最多t2水平。

陈尚涵

元豪 发表于 2022-10-6 15:06

雀食简单，暴力最多t2，你还需要学习

dolly_yos2

也来玩玩

1. #include <stdio.h>
   
2. int main(){
   
3.     int n;
   
4.     scanf("%d", &n);
   
5.     int best[n];
   
6.     scanf("%d", best);
   
7.     int max = 0;
   
8.     int input, temp;
   
9.     for(int i = 2; i <= n; ++i){
   
10.         for(int j = 0; j < i; ++j){
    
11.             scanf("%d", &input);
    
12.             if(j == 0){
    
13.                 max = temp = input + best[0];
    
14.             }else{
    
15.                 if(j == i - 1){
    
16.                 best[j] = best[j - 1] + input;
    
17.                 }else{
    
18.                     best[i - 1] = (best[j - 1] > best[j] ? best[j - 1] : best[j]) + input;
    
19.                 }
    
20.                 best[j - 1] = temp;
    
21.                 temp = best[i - 1];
    
22.                 if(temp > max) max = temp;
    
23.             }
    
24.         }
    
25.     }
    
26.     printf("%d\n", max);
    
27.     return 0;
    
28. }

复制代码

陈尚涵

dolly_yos2 发表于 2022-10-6 15:49
也来玩玩

数组的大小是固定的，第5行这个代码有问题
你这么写有点偏暴力了，算暴力吧

dolly_yos2

陈尚涵 发表于 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鱼币

数组的数量是固定的，第5行有点小问题啊，一些编译器过不去的

陈尚涵

柿子饼同学 发表于 2022-10-6 16:08
记忆化搜索也是 dp 哦

学到了

dolly_yos2

陈尚涵 发表于 2022-10-6 16:12
对不起哈，我又看了一下，可能因为你把数组命名成best不是dp，而且9-25不像dp的缘故，我以为是暴力，但是 ...

可以了解一下 VLA ，这样写起来能根据实际需要开辟数组空间大小，代码也相当简洁，主流的编译器像是 Clang 和 GCC 都是支持的（当然也不排除很可能有一些编译器是不支持的，毕竟是一个实现可以选择支持或者不支持的特性）
分支主要是要压缩存储空间和处理边界检查问题，如果做一下扩展的话（哨兵位置之类的）应该会简洁一些，不过就又需要额外的存储空间了。也能看出来某种程度上就是时间复杂度、空间复杂度和代码复杂度之间的取舍和制衡。
刚才也说了鱼币我不在乎，还是把这两个鱼币再还给您吧，不然我好像是得了便宜还卖乖

zhangjinxuan

1. #include <cstdio>
   
2. #include <algorithm>
   
3. using namespace std;
   
4. 
   
5. int main() {
   
6.         int n;
   
7.         scanf("%d", &n);
   
8.         int a[n + 1][n + 1], f[n + 1][n + 1];
   
9.         for (int i = 1; i <= n; ++i)
   
10.                 for (int j = 1; j <= i; ++j)
    
11.                         scanf("%d", &a[i][j]);
    
12.         for (int j = 1; j <= n; ++j)
    
13.                 f[n][j] = a[n][j];
    
14.         for (int i = n - 1; i >= 1; --i) {
    
15.                 for (int j = 1; j <= i; ++j) {
    
16.                         f[i][j] = a[i][j] + max(f[i + 1][j], f[i + 1][j + 1]);
    
17.                 }
    
18.         }
    
19.         printf("%d", f[1][1]);
    
20. }

复制代码

从下往上推....