iT邦幫忙

2

系列篇章統整: 好好規劃學習動態規劃(Dynamic Programming)

嗨嗨~ 大家好,
歡迎來到小馬的系列欄- 好好規劃學習動態規劃,
動態規劃在程式領域中是一個非常好用的解題技巧,
值得一學,
故這邊試著收集各類動態規劃的問題解法,
因為這個技巧太好用了,多多益善

返回主頁- 心原一馬用心經營自己的部落格,自開始寫文章以來所有篇章的總整理 #歡迎追蹤收藏

簡介- 什麼是動態規劃(Dynamic Programming)

可能會蠻多人對「動態規劃」一詞感到陌生,
簡單來說,
若解決一個問題,可以透過相似的小問題得到答案,
那麼就算是一個動態規劃解法

一般來說,動態規劃解題有二個步驟:

  1. 定義大問題與小問題的關係
  2. 使用陣列儲存小問題的解,由小到大填陣列的數值(在只需要記錄最後答案,不必記錄過程的情況下,常常可以很好的節省空間,不必把整個陣列都記下來)

超簡易範例- 費式數列

在數學上有一個有名的費式數列「1,1,2,3,5,8,13,21,…」
特色是從第三項開始,其值為前兩項的總和,
試寫程式求費式數列的第50項
想法: 用一個陣列F儲存費式數列的值,F[n]表示第n+1個費式數字
一開始將F[0],F[1]的值設成1,
然後大問題F[n]可以由小問題F[n-2],F[n-1]的值得到,
接著就由小到大填表格
範例程式:

#include <iostream>
using namespace std;
int main(){
    long long F[50];
    F[0]=1;
    F[1]=1;  
    for(int i=2;i<50;i++){ 
        F[i]=F[i-1]+F[i-2];
    }
    cout<<F[49]<<endl; //印出12586269025
}

以下收集各種動態規劃的問題

動態規劃題目收集

動態規劃經典題: 最大子陣列之和
動態規劃經典題: 循環陣列的最大子陣列之和
動態規劃經典題: 最長公共子序列(LCS)
動態規劃經典題: 最短路徑之和
動態規劃經典題: 最大正方形面積
動態規劃經典題: 帕斯卡三角形
動態規劃經典題: 01背包問題(knapsack problem)
動態規劃經典題: 給定公差,在陣列中求最長的等差子序列
動態規劃經典題: 計算有幾個正方形
動態規劃經典題: 兩道換零錢問題
動態規劃創意題: 拯救公主問題

延伸閱讀

  1. 黃建庭的教學網站>> C++演算法解題(1)>> 動態規劃(Dynamic Programming) - 這個教學網站教動態規劃的基礎觀念,講的蠻好的

尚未有邦友留言

立即登入留言