C#，动态规划（DP）丢鸡蛋问题（Egg Dropping Puzzle）的三种算法与源代码

1 扔鸡蛋问题

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

扔鸡蛋问题是计算机程序设计中的一个经典问题。从一幢楼房的不同楼层往下扔鸡蛋，用最少的最坏情况试验次数，确定鸡蛋不会摔碎的最高安全楼层。仅有一个鸡蛋供试验时，只能采用顺序查找法。有足够多的鸡蛋时，可以采用二分查找法。有多于一个但数量有限的鸡蛋时，采用动态规划方法求解。双蛋问题 (two-egg problem) 是本问题的一个特例，曾出现于谷歌的程序员面试题中。

2 源程序

using System;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
   /// <summary>
   /// Dynamic Programming
   /// Egg Dropping Puzzle
   /// </summary>
   public static partial class Algorithm_Gallery
   {
       public static int Egg_Drop(int n, int k)
       {
           if (k == 1 || k == 0)
           {
               return k;
           }
           if (n == 1)
           {
               return k;
           }
           int min = int.MaxValue;
           for (int x = 1; x <= k; x++)
           {
               int res = Math.Max(Egg_Drop(n - 1, x - 1), Egg_Drop(n, k - x));
               if (res < min)
               {
                   min = res;
               }
           }
           return min + 1;
       }

       public static int Egg_Drop_Second(int n, int k)
       {
           int[,] eggFloor = new int[n + 1, k + 1];

           for (int i = 1; i <= n; i++)
           {
               eggFloor[i, 1] = 1;
               eggFloor[i, 0] = 0;
           }

           for (int j = 1; j <= k; j++)
           {
               eggFloor[1, j] = j;
           }
           for (int i = 2; i <= n; i++)
           {
               for (int j = 2; j <= k; j++)
               {
                   eggFloor[i, j] = int.MaxValue;
                   for (int x = 1; x <= j; x++)
                   {
                       int res = 1 + Math.Max(eggFloor[i - 1, x - 1], eggFloor[i, j - x]);
                       if (res < eggFloor[i, j])
                       {
                           eggFloor[i, j] = res;
                       }
                   }
               }
           }

return eggFloor[n, k];
}

private static readonly int MAX_EGGS = 1000;
private static int[,] egg_drop_dump = new int[MAX_EGGS, MAX_EGGS];

       public static int Egg_Drop_Third(int n, int k)
       {
           if (egg_drop_dump[n, k] != -1)
           {
               return egg_drop_dump[n, k];
           }
           if (k == 1 || k == 0)
           {
               return k;
           }
           if (n == 1)
           {
               return k;
           }

           int min = int.MaxValue;
           for (int x = 1; x <= k; x++)
           {
               int res = Math.Max(Egg_Drop_Third(n - 1, x - 1), Egg_Drop_Third(n, k - x));
               if (res < min)
               {
                   min = res;
               }
           }
           egg_drop_dump[n, k] = min + 1;
           return min + 1;
       }
   }
}

3 代码格式

using System;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
    /// <summary>
    /// Dynamic Programming
    /// Egg Dropping Puzzle
    /// </summary>
    public static partial class Algorithm_Gallery
    {
        public static int Egg_Drop(int n, int k)
        {
            if (k == 1 || k == 0)
            {
                return k;
            }
            if (n == 1)
            {
                return k;
            }
            int min = int.MaxValue;
            for (int x = 1; x <= k; x++)
            {
                int res = Math.Max(Egg_Drop(n - 1, x - 1), Egg_Drop(n, k - x));
                if (res < min)
                {
                    min = res;
                }
            }
            return min + 1;
        }

        public static int Egg_Drop_Second(int n, int k)
        {
            int[,] eggFloor = new int[n + 1, k + 1];

            for (int i = 1; i <= n; i++)
            {
                eggFloor[i, 1] = 1;
                eggFloor[i, 0] = 0;
            }

            for (int j = 1; j <= k; j++)
            {
                eggFloor[1, j] = j;
            }
            for (int i = 2; i <= n; i++)
            {
                for (int j = 2; j <= k; j++)
                {
                    eggFloor[i, j] = int.MaxValue;
                    for (int x = 1; x <= j; x++)
                    {
                        int res = 1 + Math.Max(eggFloor[i - 1, x - 1], eggFloor[i, j - x]);
                        if (res < eggFloor[i, j])
                        {
                            eggFloor[i, j] = res;
                        }
                    }
                }
            }

            return eggFloor[n, k];
        }

        private static readonly int MAX_EGGS = 1000;
        private static int[,] egg_drop_dump = new int[MAX_EGGS, MAX_EGGS];

        public static int Egg_Drop_Third(int n, int k)
        {
            if (egg_drop_dump[n, k] != -1)
            {
                return egg_drop_dump[n, k];
            }
            if (k == 1 || k == 0)
            {
                return k;
            }
            if (n == 1)
            {
                return k;
            }

            int min = int.MaxValue;
            for (int x = 1; x <= k; x++)
            {
                int res = Math.Max(Egg_Drop_Third(n - 1, x - 1), Egg_Drop_Third(n, k - x));
                if (res < min)
                {
                    min = res;
                }
            }
            egg_drop_dump[n, k] = min + 1;
            return min + 1;
        }
    }
}