DP动态规划（入门，好像没入）

能用动态规划解决的问题的特点

1> 问题具有最优子结构性质： 如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质
2>无后效性 当前的若干个状态值一但确定，则此后过程的演变就之和这若干个状态的值有关，和之前是采取哪种手段或经过那条路径演变到当前的这个若干个状态， 没有关系。
2>子问题可重叠性 序偶求解的问题太可是做若干个重叠子问题的逐层递进，每个子问题的求解过程都构成一个阶段

解题思路

1>找子问题
2>确定状态
3>确定一些初始状态（边界状态）的值
4>找出状态转移方程

常见形式

1> 递归型
优点：直观，容易编写
缺点：可能会会因为递归层数太深而导致爆栈，函数调用带来额外时间开销。无法使用滚动数组节省空间。总体来说比递推型慢。
2>递推型
效率高，可能使用滚动数组节省空间

经典例题（滑雪）

来源POJ滑雪

大致意思就是让我们找到能划的最长的路线，一开始可能都以为是从最大的那个点开始划但是并不是，比如最大的点周围是1234，最多他都只能划4的长度所以并不一定在最高的位置开始划，所以所有点都有可能（当然除了最小的那个）。因为当他在某个点他的方向选择有4种，我们可以联想到深广搜（很明显的地图），一下是广搜的ac代码。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>

using namespace std;

int MAX(int p1, int p2) {
    if (p1 > p2)return p1;
    else return p2;
}

int a[2111][2111];//地图（或者说高度）
int dp[2111][2111];//状态
int h, w;//行数列数
//移动方向
int mh[4] = {1, -1, 0, 0};
int mw[4] = {0, 0, 1, -1};

int bfs(int ph, int pw) {//广搜
    int nh, nw;
    if (dp[ph][pw] > 0)return dp[ph][pw];//有值直接return
    for (int i = 0; i < 4; i++) {
        nh = mh[i] + ph, nw = mw[i] + pw;
        if (nh > 0 && nw > 0 && nh <= h && nw <= w &&//条件：边界和往小值划
            a[nh][nw] > -1 && a[ph][pw] > a[nh][nw]) {
            dp[ph][pw] = MAX(dp[ph][pw], bfs(nh, nw) + 1);
            //MAX左边是原来的，右边是新广搜出来的状态，我们要选择最大的状态
            //第一次广搜的时候前面是0所以会选择广搜出来的值，后面疯狂取大
        }
    }
    return dp[ph][pw];//搜完之后返回dp状态，让他能在上面的if里直接返回，节省时间
}


int main() {
    scanf("%d %d", &h, &w);//输入地图的行数和列数
    memset(dp, 0, sizeof dp);//初始化保险
    memset(a, -1, sizeof(a));//将a都变成-1，来确定边界
    .0
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            scanf("%d", &a[i][j]);//输入地图
        }
    }
    int m_last = 0;//最长距离
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            m_last = MAX(m_last, bfs(i, j) + 1);
            //将所有的点都dfs一遍取大
        }
    }
    printf("%d\n", m_last);
    return 0;
}