[数据结构与算法] 动态规划2---线性dp

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 动态规划2---线性dp -> 正文阅读

[数据结构与算法]动态规划2---线性dp

本篇文章总结动态规划的第二大类问题，即线性dp问题。

题目1：数字三角形

题目描述：

这道题目怎么想？我们还是从y总的dp分析法出发。

?在定义坐标的行和列时，我们如下的定义方式：

?这样的话就好理解了：

#include<bits/stdc++.h>
using namespace std;

const int INF=1e9;
int a[505][505];
int f[505][505];
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=i;j++)
        cin>>a[i][j];
        
    for(int i=0;i<=n;i++)
      for(int j=0;j<=i+1;j++)//这个范围要往后开一些，否则的话很可能就会导致计算错误
         f[i][j]=-INF;

   f[1][1]=a[1][1];
    for(int i=2;i<=n;i++)
      for(int j=1;j<=i;j++)
      {
          f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);//状态转移方程求最大值
      }
    
    int res=-INF;
    
    for(int i=1;i<=n;i++)
       res=max(res,f[n][i]);
    
    cout<<res;
    return 0;
}