算法提高课汇总

算法思路

相比于AcWing 1015. 摘花生 问题, 不同点在于 :

• 没有限制每一步的方向, 但限制总步数为$2N - 1$

• 计算最小值而不是最大值

$2N - 1$

首先考虑$2N - 1$的含义 : 考虑每一步都向下/右, 发现总步数恰好为$2N - 1$, 两者等价.

计算最小值

在摘花生问题中, 因为计算最大值而花生数目数组w[][]初始值为0. 所以在计算过程中尽管计算了
不存在的第0行和第0列, 但对最终结果没有影响. 但本题计算最小值, 所以要对边界进行一定处理.
对除了(1,1)的临近(0,1)&(1,0)外, 其他的(0,i)&(0,j)初始化为INF. 因为只有第一步进入
(1,1)时不用考虑边界问题.

此外本题与摘花生没有区别, 所以可以直接按类似思路编写代码.

代码实现

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, INF = 1e9 + 10;

int n;
int w[N][N];
int dp[N][N];

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

    //初始化边界
    for( int i = 2; i <= n; i ++ )  
        dp[i][0] = dp[0][i] = INF;

    for( int i = 1; i <= n; i ++ )
        for( int j = 1; j <= n; j ++ )
        {
            dp[i][j] = min( dp[i-1][j], dp[i][j-1] ) + w[i][j];
        }

    cout << dp[n][n] << endl;

    return 0;
}