【算法|动态规划 | 线性dp | 数字三角形模型No.1】AcWing1015.摘花生 & AcWing898.数字三角形 & AcWing1027.方格取数 & AcWing275.传纸条

傷城~ 2024-04-27 06:52 52阅读 0赞

> 个人主页：[兜里有颗棉花糖][Link 1]  
> 欢迎 点赞? 收藏✨ 留言✉ 加关注?本文由 [兜里有颗棉花糖][Link 1] 原创  
> 收录于专栏【[AcWing算法提高学习专栏][AcWing]】  
> ?本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助  
> ?**希望我们一起努力、成长，共同进步**。

#### 目录 ####

*  一、AcWing1015. 摘花生
 *   *  解题代码
 *  二、AcWing898. 数字三角形
 *   *  解题代码1
     *  解题代码2
 *  三、AcWing1018. 最低通行费
 *   *  解题代码
 *  四、AcWing 1027. 方格取数
 *   *  解题代码
 *  五、AcWing 275. 传纸条
 *   *  解题代码

## 一、AcWing1015. 摘花生 ##

**原题链接**：[点击直接跳转到该题目][Link 2]

**状态表示：**

*  `dp[i][j]`表示到达`(i,j)`位置是所能获得花生数量的最大值。

**状态转移方程：**

*  `dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]) + arr[i]`

**返回值：**

*  `dp[n][n]`

### 解题代码 ###

#include<iostream>
    #include<vector>
    using namespace std;
    
    const int N =110;
    
    int main()
    {
        
        int T;
        cin >> T;
        while(T--)
        {
        
            vector<vector<int>> arr(N,vector<int>(N));
            vector<vector<int>> dp(N,vector<int>(N));
            int R,C;
            cin >> R >> C;
            for(int i = 0;i < R;i++)
            {
        
                for(int j = 0;j < C;j++)
                    cin >> arr[i][j];
            }
            // 创建dp表
            for(int i = 1;i <= R;i++)
            {
        
                for(int j = 1;j <= C;j++)
                {
        
                    dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]) + arr[i - 1][j - 1];
                }
            }
            cout << dp[R][C] << endl;
        }
        return 0;
    }

## 二、AcWing898. 数字三角形 ##

**原题链接：[点击直接跳转到该题目][Link 3]**

**状态表示：**

*  **`dp[i][j]`表示从`右下角(n,n)`走到`(i,j)`所有走法中路径和的最大值。**

**状态转移方程：**

*  `dp[i][j] = max(dp[i + 1][j],dp[i + 1][j + 1]) + arr[i][j]`

**返回值：**

*  `dp[1][1]`

### 解题代码1 ###

#include<iostream>
    #include<vector>
    #include<climits>
    using namespace std;
    
    const int N = 510;
    int arr[N][N];
    
    int main()
    {
        
        int n;
        scanf("%d",&n);
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= i;j++)
                scanf("%d",&arr[i][j]);
        
        // 创建dp表
        vector<vector<int>> dp(N,vector<int>(N));
        for(int i = n;i >= 1;i--) dp[n][i] = arr[n][i];
        for(int i = n - 1;i >= 1;i--)
            for(int j = n - 1;j >= 1;j--)
                dp[i][j] = max(dp[i + 1][j],dp[i + 1][j + 1]) + arr[i][j];
        printf("%d\n",dp[1][1]);
        return 0;
    }

### 解题代码2 ###

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
     
    const int N = 510;
    int nums[N][N];
    int dp[N][N];
    int INF = 1e9;
    
    using namespace std;
    
    int main()
    {
        
        int n,ret = -INF;
        cin >> n;
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= i;j++)
                cin >> nums[i][j];
        
        // dp 初始化
        for(int i = 1;i <=n ;i++) 
        	dp[i][0] = -INF,dp[i][i + 1] = -INF;
        dp[1][1] = nums[1][1];
    
    	// dp填表
        for(int i = 2;i <= n;i++)
            for(int j = 1;j <= i;j++)
            {
        
                dp[i][j] = max(dp[i - 1][j - 1],dp[i - 1][j]) + nums[i][j];
                ret = max(ret,dp[i][j]);
            }
        cout << ret << endl;
        return 0;
    }

## 三、AcWing1018. 最低通行费 ##

**原题链接：[点击直接跳转到该题目][Link 4]**

### 解题代码 ###

#include<iostream>
    #include<vector>
    #include<climits>
    using namespace std;
    
    const int N = 110;
    
    int main()
    {
        
        int n;
        cin >> n;
        vector<vector<int>> arr(N,vector<int>(N));
        for(int i = 0;i < n;i++)
            for(int j = 0;j < n;j++)
                cin >> arr[i][j];
        
        // 创建dp表
        vector<vector<int>> dp(N,vector<int>(N));
        
        // dp初始化
        for(int j = 0;j <= n;j++) dp[0][j] = INT_MAX;
        for(int i = 2;i <= n;i++) dp[i][0] = INT_MAX;
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= n;j++)
                dp[i][j] = min(dp[i][j - 1],dp[i - 1][j]) + arr[i - 1][j - 1];
        cout << dp[n][n] << endl;
        return 0;
    }

## 四、AcWing 1027. 方格取数 ##

**原题链接：[点击直接跳转到该题目][Link 5]**

### 解题代码 ###

#include<iostream>
    using namespace std;
    
    const int N = 20;
    int arr[N][N],dp[N][N][N][N];
    int x,y,z;
    
    int main()
    {
        
        int n;
        scanf("%d",&n);
        while(cin >> x >> y >> z)
        {
        
            if(x == 0 && y == 0 && z == 0) break;
            arr[x][y] = z;
        }
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= n;j++)
                for(int k = 1;k <= n;k++)
                    for(int l = 1;l <= n;l++)
                    {
        
                        dp[i][j][k][l] = max(max(dp[i - 1][j][k - 1][l],dp[i - 1][j][k][l - 1]),max(dp[i][j - 1][k - 1][l],dp[i][j - 1][k][l - 1])) + arr[i][j] + arr[k][l];
                        if(i == k && j == l) dp[i][j][k][l] -= arr[i][j]; 
                    }
        printf("%d\n",dp[n][n][n][n]);
        return 0;
    }

## 五、AcWing 275. 传纸条 ##

**原题链接：[点击直接跳转到该题目][Link 6]**

### 解题代码 ###

#include<iostream>
    using namespace std;
    
    const int N = 55;
    int arr[N][N],dp[N][N][N][N];
    
    int main()
    {
        
        int m,n;
        cin >> m >> n;
        for(int i = 1;i <= m;i++)
            for(int j = 1;j <= n;j++)
                scanf("%d",&arr[i][j]);
        for(int i = 1;i <= m;i++)
            for(int j = 1;j <= n;j++)
                for(int k = 1;k <= m;k++)
                    for(int l = 1;l <= n;l++)
                    {
        
                        dp[i][j][k][l] = max(max(dp[i - 1][j][k - 1][l],dp[i - 1][j][k][l - 1]),max(dp[i][j - 1][k - 1][l],dp[i][j - 1][k][l - 1])) + arr[i][j] + arr[k][l];
                        if(i == k && j == l) dp[i][j][k][l] -= arr[i][j];
                    }
        printf("%d\n",dp[m][n][m][n]);
    }

[Link 1]: https://xiaofeizhu.blog.csdn.net/
[AcWing]: https://blog.csdn.net/m0_74352571/category_12481646.html
[Link 2]: https://www.acwing.com/problem/content/1017/
[Link 3]: https://www.acwing.com/problem/content/900/
[Link 4]: https://www.acwing.com/problem/content/1020/
[Link 5]: https://www.acwing.com/problem/content/1029/
[Link 6]: https://www.acwing.com/problem/content/277/