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

陈尚涵

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

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

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

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

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

输入样例：

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

输出样例：

30

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

陈尚涵

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

tommyyu

#include<iostream>
using namespace std;
int a[200][200], n;
int dp(int s, int x, int y) {
        if(x == n-1) {
                return s + a[x][y];
        }
        return max(dp(s+a[x][y], x+1, y), dp(s+a[x][y], x+1, y+1));
}
int main()
{
        cin>>n;
        for(int i=0; i<n; ++i) {
                for(int j=0; j<=i; ++j) {
                        cin>>a[i][j];
                }
        }
        cout<<dp(0, 0, 0);
        return 0;
}

元豪

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

也来玩玩

#include <stdio.h>
int main(){
    int n;
    scanf("%d", &n);
    int best[n];
    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[0];
            }else{
                if(j == i - 1){
                best[j] = best[j - 1] + input;
                }else{
                    best[i - 1] = (best[j - 1] > best[j] ? best[j - 1] : best[j]) + input;
                }
                best[j - 1] = temp;
                temp = best[i - 1];
                if(temp > max) max = temp;
            }
        }
    }
    printf("%d\n", max);
    return 0;
}

陈尚涵

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

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
        int n;
        scanf("%d", &n);
        int a[n + 1][n + 1], f[n + 1][n + 1];
        for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= i; ++j)
                        scanf("%d", &a[i][j]);
        for (int j = 1; j <= n; ++j)
                f[n][j] = a[n][j];
        for (int i = n - 1; i >= 1; --i) {
                for (int j = 1; j <= i; ++j) {
                        f[i][j] = a[i][j] + max(f[i + 1][j], f[i + 1][j + 1]);
                }
        }
        printf("%d", f[1][1]);
}

从下往上推....