【37. 线性DP】

• 线性DP有可能是一维线性和二维线性

• 动态规划是多维状态，可能是一维、二维、三维等

• DP的下标一般是从1开始

• 计算过程中涉及到了i-1下标，那么i 的下标尽量从1开始,如果没有涉及i-1那么下标从0开始

• 动态规划的复杂度 = 状态数量 * 转移的计算量（算每一个状态需要计算的量）
  
  思路：

• 一般就是就是向下走，和向上爬两种思路，向上爬的思路可以不需要考虑边界问题。

• 而当向下走的时候，需要考虑边界问题。也就是对于f[2][1]的时候，f[1]f[0]并没有设置这个值，默认为0，题中的数字有负数，则会出现错误的最大值。需要对于f进行重置，置为Integer.MIN_VALUE.

题目

解法1：向下走

#include 
#include 
using namespace std;

const int N = 510, INF = 1e9;  //INF设置为正无穷，-INF则为负无穷
int a[N][N], f[N][N];          //f[N][N]表示从起点到这个点的最大值，a[N][N]表示每个具体点的值
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 ++)   //因为有负数，所以应该将两边也设为-INF
            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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

解法2：往上走

#include 
#include 
using namespace std;

#include
using namespace std;

const int N=510;
int f[N][N];
int n;

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>f[i][j];
        }
    }

    for(int i=n;i>=1;i--){
        for(int j=i;j>=1;j--){
            f[i][j]=max(f[i+1][j] ,f[i+1][j+1])+f[i][j];
        }
    }
    cout<<f[1][1]<<endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

总结：

• 如果是倒序的话，方向是从右向左，从上到下，首先i = n的时候， 最后一排会出现f[i][j] = a[i][j]的情况，然后处理倒数第二行时，他是max(f[i+1][j],f[i+1][j+1])对比的下方和右下方，即使是最右边的元素也不会处理到边界问题，所以可以不对f初始化为-INF
• 如果正序dp的话，他选择的方式是max(f[i-1][j-1],f[i-1][j])，是左上角和上方，这样的话最左边的元素会处理到边界，所以需要处理边界问题。