1015.摘花生(简单)

题目描述：

给定行数为\(R\)，列数为\(C\)的矩形花生地，每次可以向东或向南走，到了过一株花生苗就能摘走该它上面所有的花生。问从\((1,1)\)走到\((R,C)\)最多可以摘多少花生。

思路：

看到题意不难想到是动态规划。
由于题意里说了只能向东(右)或向南(下)走，所以对于上个状态到这个状态有两种决策：向上或向左
明白这点后，就可以直接使用\(y\)式\(DP\)分析法：

得到状态转移方程：

\(f[i,j]=max(f[i-1,j],f[i,j-1])+w[i,j]\)

Code：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int w[N][N];
int f[N][N];

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                scanf("%d", &w[i][j]);
        
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j];
        
        printf("%d\n", f[n][m]);
    }
    return 0;
}

1018.最低通行费(简单)

题目描述：

有一个商人，在\(N×N\)的房间中\((1,1)\)处，每次可以向下或向右移动，到了每个位置都需要支付\(w[i,j]\)元，最多走\(2×N-1\)步，问走到\((N,N)\)最少花费是多少。

思路：

题意中最多走\(2×N-1\)步的意思就是不能走回头路，明白这点后就跟\(1015\).摘花生差不多了。
由于题意里说了只能向右或向下走，所以对于上个状态到这个状态有两种决策：向左或向上
要注意的是边界情况：

1. 在第一行中，上一步只能是由\((x,y-1)\)转移得到
2. 在第一列中，上一步只能是由\((x-1,y)\)转移得到

用\(y\)式\(DP\)分析法，可以得到：
\(f[i,j]=min(f[i-1,j],f[i,j-1])+w[i,j]\)

Code:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;
const int INF = 0x3f3f3f3f;

int n;
int w[N][N];
int f[N][N];

int main()
{
    scanf("%d", &n);
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            scanf("%d", &w[i][j]);
    // 初始化
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            f[i][j] = INF;
    f[1][1] = w[1][1];
            
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
        {
            if (i > 1) f[i][j] = min(f[i][j], f[i - 1][j] + w[i][j]);  // 不在第一行
            if (j > 1) f[i][j] = min(f[i][j], f[i][j - 1] + w[i][j]);  // 不在第一列
        }
            
    printf("%d", f[n][n]);
    
    return 0;
}

1.1数字三角形模型