C#，动态规划（DP）金矿问题（Gold Mine Problem）的算法与源代码

1 金矿问题（Gold Mine Problem）

���定一个N*M尺寸的金矿，每个点都有一个非负数表示当前点所含的黄金数目，最开始矿工位于第一列，但是可以位于任意行。矿工只能向右，右上，右下三个方向移动。问该如何安排路线使得所挖的黄金的数量最多？

2 源程序（2种算法）：

using System;

using System.IO;

using System.Text;

using System.Collections;

using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm

{

    public static partial class Algorithm_Gallery

    {

        private static int Collect_Gold(int[,] gold, int r, int c, int n, int m)

        {

            // Base condition.

            if ((r

            {

                return 0;

            }

            int rightUpperDiagonal = Collect_Gold(gold, r - 1, c + 1, n, m);

            int right = Collect_Gold(gold, r, c + 1, n, m);

            int rightLowerDiagonal = Collect_Gold(gold, r + 1, c + 1, n, m);

            return gold[r, 0] + Math.Max(Math.Max(rightUpperDiagonal, rightLowerDiagonal), right);

        }

        public static int Get_Maxium_Gold(int[,] gold)

        {

            int n = gold.GetLength(0);

            int m = gold.GetLength(1);

            int maxGold = 0;

            for (int i = 0; i

            {

                int goldCollected = Collect_Gold(gold, i, 0, n, m);

                maxGold = Math.Max(maxGold, goldCollected);

            }

            return maxGold;

        }

        private static int Collect_Gold(int[,] gold, int r, int c, int n, int m, int[,] dp)

        {

            if ((r

            {

                return 0;

            }

            if (dp[r, 0] != -1)

            {

                return dp[r, 0];

            }

            int rightUpperDiagonal = Collect_Gold(gold, r - 1, c + 1, n, m, dp);

            int right = Collect_Gold(gold, r, c + 1, n, m, dp);

            int rightLowerDiagonal = Collect_Gold(gold, r + 1, c + 1, n, m, dp);

            return gold[r, 0] + Math.Max(Math.Max(rightUpperDiagonal, rightLowerDiagonal), right);

        }

        public static int Get_Maxium_Gold_Second(int[,] gold)

        {

            int n = gold.GetLength(0);

            int m = gold.GetLength(1);

            int maxGold = 0;

            int[,] dp = new int[n, m];

            for (int row = 0; row

            {

                for (int col = 0; col

                {

                    dp[row, col] = -1;

                }

            }

            for (int i = 0; i

            {

                int goldCollected = Collect_Gold(gold, i, 0, n, m, dp);

                maxGold = Math.Max(maxGold, goldCollected);

            }

            return maxGold;

        }

    }

}

 

3 源程序

using System;using System.IO;using System.Text;using System.Collections;using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm{    public static partial class Algorithm_Gallery    {        private static int Collect_Gold(int[,] gold, int r, int c, int n, int m)        {            // Base condition.            if ((r