← 筆記
LeetCode

《圖說演算法-使用C#》要點摘錄 - 「常見演算法」

書名：《圖說演算法-使用C#》

作者：吳燦銘、胡昭民

所讀版本：博碩文化

分治法

  • 反覆分割問題，使子問題規模不斷縮小，直到這些子問題足夠簡單到可以解決，最後將各子問題的解合併得到原問題的解答

遞歸

  • 一個函數由自身定義或呼叫

  • 必須要有2個條件

    • 中止遞歸出口
    • 遞歸執行過程

  • 例子：菲波那契數列

    •   public static int Fibonacci(int idx)
  {
      if (idx == 0) { return 0; }
      else if (idx == 1) { return 1; }
      else { return Fibonacci(idx - 1) + Fibonacci(idx - 2); }
  }

動態規劃（Dynamic Programming）

  • 類似分治法，但會利用某種數據結構將子問題的解保存起來
  • 當解決一樣的子問題時，就可以直接從數據結構中得到子問題的解並返回，而不需要重新解決一次子問題。
  • 例子：優化的菲波那契數列 
    •   static Dictionary<int, int> fibonacciResultMemo = new Dictionary<int, int>()
  {
      {0, 0 },
      {1, 1 }
  };
  
  public static int Fibonacci(int idx)
  {
      if (fibonacciResultMemo.ContainsKey(idx)) { return fibonacciResultMemo[idx]; }
      else
      {
          int res = Fibonacci(idx - 1) + Fibonacci(idx - 2);
          fibonacciResultMemo.Add(idx, res);
          return res;
      }
  }

迭代

  • 結果無法用公式一次求解，需要利用迴圈反覆運算
  • 迴圈結構的三個條件：
    • 標記迴圈起點和進度的變數
    • 循環條件
    • 迴圈變數的增減值
  • 例子：計算階層 
    •   public static int Stairs(int targetStair)
  {
      int sum = 1;
      for (int i = 0; i <= targetStair; i++)
      {
          sum = 1;
          for (int j = i; j > 0; j--)
          {
              sum = sum * j;
          }
      }
      return sum;
  }

Pascal’s Triangle

  • rC0 = 1 => 每一列的第0欄的值一定為1

  • rCn = rCn-1 * (r - n + 1)/n => 某欄某列元素值公式

    • r = row
    • n = column

回溯法

  • 窮舉法的一種，但在發現目標不正確後馬上返回上一層，而不遞歸到下一層
    • 作者的例子是只能局限在知道終點在起點的方位（右下角）的前提下才能生效的，但如果不知道起、終點的位置，實際上只能使用DFS進行搜索。
    • 修改版： 
      •   static void Main(string[] args)
  {
      (int x, int y) start = (1, 1);
      (int x, int y) exit = (8, 2);
      int[,] maze = new int[10, 12]
      {
          {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
          {1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1 },
          {1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1 },
          {1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1 },
          {1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1 },
          {1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1 },
          {1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1 },
          {1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1 },
          {1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1 },
          {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
      };
  
      FindPathInMaze(start, exit, maze);
  
      Console.WriteLine();
  }
  public static void FindPathInMaze((int x, int y) startPos, (int x, int y) goalPos, int[,] maze)
  {
      Stack<(int x, int y)> pathStack = new Stack<(int x, int y)>();
      pathStack.Push(startPos);
  
      while (pathStack.Count > 0)
      {
          (int x, int y) currPath = pathStack.Pop();
  
          //Reach Goal, Break Loop
          if (currPath.x == goalPos.x && currPath.y == goalPos.y)
          {
              maze[currPath.x, currPath.y] = 2;
              break;
          }
  
          //Set Current 
          maze[currPath.x, currPath.y] = 2;
  
          if (maze[currPath.x - 1, currPath.y] == 0)
          {
              pathStack.Push((currPath.x - 1, currPath.y));
          }
          if (maze[currPath.x + 1, currPath.y] == 0)
          {
              pathStack.Push((currPath.x + 1, currPath.y));
          }
          if (maze[currPath.x, currPath.y + 1] == 0)
          {
              pathStack.Push((currPath.x, currPath.y + 1));
          }
          if (maze[currPath.x, currPath.y - 1] == 0)
          {
              pathStack.Push((currPath.x, currPath.y - 1));
          }
      }
  }

貪心算法

  • 只考慮局部而不考慮大局，通過每一次計算都選擇當前最好的選擇，逐步逼近目標
  • 不能保證最後的解是最佳解