Data structure & Algorithm
  • Initial page
  • 1212
  • 121231
  • 2.algorithm
    • 2.1.backtracking
      • 2.1.1.連續序列的排列組合(可能會重複)
      • 2.1.3.一串數列中任取n個數字, 總共有幾種組合
      • 2.1.2.一串數列中取n個數字, 共有幾種組合
    • 2.5.Quick sort
    • 2.6.2.6.廣度優先搜尋 (Breadth-first Search)
    • 2.2.Binary Search
    • 2.1.Backtracking
    • 2.4.河內塔 (Tower of Hanoi)
    • 2.7.動態規劃
    • 2.8.深度優先搜尋 (Depth-first Search)
    • 2.7.二分搜尋法
    • 2.3.分治法 (Divide and Conquer)
  • 2.Count and Say
  • 1.Leetcode Algorithm Practice
  • 2-count-and-say
    • c-solution
    • javascript-solution
  • Algorithm
  • 123
Powered by GitBook
On this page
  • 1.Introduction
  • 2.使用動態規劃的時機
  • 3.例子

Was this helpful?

  1. 2.algorithm

2.7.動態規劃

Previous2.4.河內塔 (Tower of Hanoi)Next2.8.深度優先搜尋 (Depth-first Search)

Last updated 5 years ago

Was this helpful?

1.Introduction

  • 動態規劃是的延伸

  • 當遞迴分割出來的問題, 一而再、再而三出現, 就運用記憶法儲存這些問題的答案, 避免重複求解, 以空間換取時間

  • 動態規劃的過程, 就是反覆地讀取數據、計算數據、儲存數據

2.使用動態規劃的時機

  • 計算各種組合的數量

  • 取得到現階段的某種可能數字 (例如: 最大值)

3.例子

  • 1.

  • 2.

  • 3.地圖

    • 只能向下走或向右走, 有幾種可以到達目的地的走法?

    • 由於可以先知道前一步有多少種組合, 前一步又可以從前前一步的組合推得...

      • P[i][j] = P[i - 1][j] + P[i][j - 1]

分治法
爬樓梯