iT邦幫忙

2021 iThome 鐵人賽

DAY 16
1
自我挑戰組

【帶你輕鬆入門演算法-Leetcode】系列 第 16

【第十六天 - 動態規劃 介紹】

Q1. 動態規劃(Dynamic Programming)是什麼 ?

  • Dynamic programming,簡稱DP,是一種多階段決策出最佳解的方法,他會將問題分成子問題、子子問題...,拆成多個子問題進行求解,並且求出最佳解

  • DP 可以大致理解為是分治法 + 記憶法

    • 首先定義出將大問題切割為子問題的方法。
    • 當一個子問題的答案被計算出來後,採取記憶法,將答案儲存在記憶體中,避免未來重複計算。
  • 以計算費氏數列為例:
    https://ithelp.ithome.com.tw/upload/images/20210916/20140592kP3sIRgybc.png

  • 計算 f(5):
    https://ithelp.ithome.com.tw/upload/images/20210916/20140592ecvY7JHRxJ.png

  • 可以看到圖中綠色的數字都會重複計算,而隨著 n 越大,重複計算的會越多。

  • 此時可以將計算過的答案保存在記憶體中,用空間換取時間,大幅節省效能。

參考資料:https://www.gushiciku.cn/pl/pKW7/zh-tw

參考資料:https://codertw.com/程式語言/586675/

Q2. 學會 動態規劃概念可以做什麼 ?

  • 動態規劃問題在程式競技比賽中,是經典的問題,常見的問題有:

Lab. 明天要解的題目:53. Maximum Subarray

  • 題目敘述:https://leetcode.com/problems/maximum-subarray/

  • 題目敘述:

    • 題目會給一個 nums 的 list,需要找出至少一個數字的連續值,他們相加的結果會是最大的

    https://ithelp.ithome.com.tw/upload/images/20210916/20140592bFVnlKI9Pf.png

  • 測資的 Input/Output

    • 會給一個 nums 的 list,需要回傳連續相加最大的值
      https://ithelp.ithome.com.tw/upload/images/20210916/20140592UM2t0ez2iq.png
  • 題目的條件

    • list 長度在 1~30000 間
    • 每個值借於 -100000 ~ 100000 間
      https://ithelp.ithome.com.tw/upload/images/20210916/20140592Z5mhJoWGAd.png
  • 看完題目,你要思考:

    • 你是否把每個 list 值相加結果儲存起來?
    • 你是否能不使用額外使用 list 空間解決這一題?
    • 什麼算法可以不造成超時?

上一篇
【第十五天 - Linked list 題目分析】
下一篇
【第十七天 - 動態規劃 題目分析】
系列文
【帶你輕鬆入門演算法-Leetcode】30

尚未有邦友留言

立即登入留言