矩阵最优路线DP

母题：矩阵中每个点有权值，每经过一个点就累加权值，求从a点到b点的最优（最大）路线。

题型1：

从左上到右下，只能向下或者向右

for 行

　　for 列

　　　　dp=max dp左,dp上;

扫一遍就行

有时可能会是bfs+记忆化搜索，仔细看题

题型2：

从左上到右上，只能向下、上、右，不能走重复的点。

这种题一定要单独求解每一列从左、上转移和从左、下转移的dp，最后求最大值（如果不单独求解，就会出现走重复点的情况，理解一下状态转移的概念就明白了）。

        for(int j=;j<=n;j++)

            dp[j][]+=dp[j-][];

        for(int j=;j<=m;j++)

        {

            int temp[];

            for(int i=;i<=n+;i++)

                temp[i]=-INF;

            for(int i=;i<=n;i++)

                temp[i]=dp[i][j];

            for(int i=n;i>=;i--)

                temp[i]+=Max(dp[i][j-],temp[i+]);

            for(int i=;i<=n;i++)

                dp[i][j]+=Max(dp[i-][j],dp[i][j-]);

            for(int i=;i<=n;i++)

                dp[i][j]=Max(dp[i][j],temp[i]);

        }

//TODO

巴特西

矩阵最优路线DP

最新文章

热门文章