dp算法入门（闫氏dp分析法）

dp算法

• 什么是dp
• 一、核心思想
• 二、dp入门
  • 1.线性dp
  • 2 .未完待续
• 总结

  ---

  什么是dp

  dp即是动态规划，是一种把问题分成若干个有关联的子问题来求解复杂问题的方法。dp常常适用于有重叠的子问题和最有子结构性质的问题(★ dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.)简单来说，dp就是将复杂问题分成小问题然后表示每种问题的‘状态’并加以计算。

  一、核心思想

  动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。

  二、dp入门

  1.线性dp

  T1:acwing898（模板）

  题目描述:给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

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

  输入格式

  第一行包含整数 n，表示数字三角形的层数。

  接下来 n 行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。

  输出格式

  输出一个整数，表示最大的路径数字和。

  对于此题，先来研究一般性，假设我们从最后一行开始（最后一行每一个数都可能成为起点），依次往上走，知道走到第一个点（不妨将图记作g[][],第一个点记作g[1][1],为什么不从0开始作为下标，后面会分析）假设一直往上走，走到了g[i][j]这个点，那么对于g[i][j]，来看它来源

              g[i][j]

          g[i+1][j]  g[i+1][j+1]

  由题意，可以知道点g[i][j]，只能由g[i+1][j],g[i+1][j+1]两个点直接得到，我们不妨定义数组f[][]，让f[i][j]表示为所有从最后一行走到点i，j的距离的最大值。这个f数组就是这题的状态表示,那么怎么计算f[i][j]呢，我们已经推出了点（i，j）只能由（i + 1，j）和（i + 1，j + 1）两个点到，所以怎么求     f[i][j]就转化为了只需要求f[i + 1][j] 和 f[i + 1][j + 1]的最大值，再加上i，j上的值，即g[i][j]即可，公式表达如下：

  代码如下：

  #include #include #include using namespace std;const int N = 510;int g[N][N], f[N][N], n;//g数组存图，f数组表示所有以（i，j）为终点的方案的数字和最大值int main(){    scanf("%d", &n);        for(int i = 1; i