動態規劃的引入

来源:https://www.cnblogs.com/Echo-djc/archive/2022/08/14/16585550.html
-Advertisement-
Play Games

動態規劃的引入 動態規劃(Dynamic Programming,DP)是運籌學的一個分支,是求解決策過程最優化的過程。20世紀50年代初,美國數學家貝爾曼(R.Bellman)等人在研究多階段決策過程的優化問題時,提出了著名的最優化原理,從而創立了動態規劃。動態規劃的應用極其廣泛,包括工程技術、經 ...


動態規劃的引入

動態規劃(Dynamic Programming,DP)是運籌學的一個分支,是求解決策過程最優化的過程。20世紀50年代初,美國數學家貝爾曼(R.Bellman)等人在研究多階段決策過程的優化問題時,提出了著名的最優化原理,從而創立了動態規劃。動態規劃的應用極其廣泛,包括工程技術、經濟、工業生產、軍事以及自動化控制等領域,併在背包問題、生產經營問題、資金管理問題、資源分配問題最短路徑問題和複雜系統可靠性問題等中取得了顯著的效果。

​ ——百度百科

動態規劃與分治法相似,都是通過組合子問題來求解原問題。根據演算法導論,Programming 譯作“表格法”而不是“編寫程式”,“動態規劃”這個名字網路上有段子說是用來討要經費的。

包含如下特征:

  • 階段 問題被劃分為若幹階段,每階段受先前階段影響
  • 狀態 描述該階段特定子問題的若幹變數
  • 決策 從一個狀態演變到下一階段某個狀態的選擇
  • 最優子結構 一個最優化策略的子策略總是最優的
  • 無後效性 已經求解的子問題,不會再受到後續決策的影響

OI 中 DP 的含義被極大地擴展了,下麵提取兩大核心特征

  • 狀態 一個含義清晰且獨立 (即無後效性) 的子問題 $I $

    ▶ 使用 \(f_I\) 表示子問題 $ I$ 的答案

    ▶ 可能需要引入輔助子問題 $g_J, h_K, · · · $

  • 轉移 答案 \(f_I\) 通過狀態轉移方程由其它子問題共同計算得到

    ▶ 以狀態為點,轉移為邊,構成有向無環圖 (DAG)

    ▶ 邊界條件與平凡子問題

    ▶ 解空間中的任意元素都被恰當考慮

如何理解最後一句話?按照問題類型分類

  • 最優化 (k-優) 最優解能被考慮到,這依賴於最優子結構
  • 計數 (概率, 期望) 計數對象 (事件) 能被不重不漏地處理

使用動態規劃需要滿足以下性質

1.最優子結構性質。動態規划下一階段的最優解應該能由前面已經算出的各階段的最優解導出。

舉個簡單的例子。下麵是一個地圖,我們要找一條從左下角(起點)到右上角(終點)、只向右和向上走的路徑。

img

如果要讓路徑經過的數字總和最大,那麼最優路徑是下麵這條:

img

可以驗證,對於最優路徑上的任意一點,最優路徑從起點到該點的部分,也正是從起點到該點的所有路徑中數字總和最大的那一條。這就叫「滿足最優子結構」。

現在換一個「最優」的標準,要求路徑經過的數字總和的絕對值最小。那麼最優路徑是下麵這條:

img

但是,對於最優路徑上 -4 這個點,最優路徑從起點到該點的部分,卻不是從起點到該點的所有路徑中,數字總和的絕對值最小的那一條,因為下麵這條路徑上數字總和的絕對值更小:

img

這就叫「不滿足最優子結構」。

常見的最優化問題,問法一般都是「最大」「最小」,不太會出現「絕對值最小」這種奇葩的最優化標準。而問「最大」「最小」的問題,一般都是滿足最優子結構的。 慄子來自知乎 作者:王贇 Maigo)

2.無後效性。動態規劃要求已經求解出的子問題不能受後續階段的影響,也就是說,動態規劃時對於狀態空間的遍歷應該構成一個有向無環圖。

例如CSP-J 2020 方格取數 本題可以向上向下走,如果直接設計 \(f(i, j)\) 的狀態表示走到格子 \((i, j)\),那麼如下圖,狀態轉移形成環形,會產生後效性。

此時進行動態規劃時就要設計一個無後效性的狀態,如在原狀態 \(f(i, j)\) 的基礎上加一維表示方向。

3.子問題重疊。動態規劃之所以優於爆搜,就是因為它以空間換時間的形式記錄了前面所有狀態的最優解。


狀態、階段和決策則是動態規劃的三要素。動態規劃將相同的計算作用在各階段的同類子問題,這種計算被稱為狀態轉移方程,其實也就是決策,將當前狀態轉移到下一狀態或更新下一狀態,或是根據前面的狀態計算當前狀態。


一般都是通過數字三角形引入:

Number Triangles

題目描述

觀察下麵的數字金字塔。

寫一個程式來查找從最高點到底部任意處結束的路徑,使路徑經過數字的和最大。每一步可以走到左下方的點也可以到達右下方的點。

     7 
   3   8 
 8   1   0 
2   7   4   4 
4   5   2   6   5 

在上面的樣例中,從 \(7 \to 3 \to 8 \to 7 \to 5\) 的路徑產生了最大

輸入格式

第一個行一個正整數 \(r\) ,表示行的數目。

後面每行為這個數字金字塔特定行包含的整數。

輸出格式

單獨的一行,包含那個可能得到的最大的和。

樣例 #1
樣例輸入 #1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
樣例輸出 #1
30

【數據範圍】 對於 \(100\%\) 的數據,\(1\le r \le 1000\),所有輸入在 \([0,100]\) 範圍內。

方法一:遞歸

int solve(int i, int j) {
    return a[i][j] + (i == n ? 0 : max(solve(i + 1, j), solve(i + 1, j + 1)));
}

如果數據範圍很小,可以考慮爆搜,所有路徑條數為 \(2^{n - 1}\) ,所以時間複雜度為 \(\Theta(2^n)\) ,無法接受。

方法二:遞推

時間複雜度 \(\Theta(n^2)\)

#include<bits/stdc++.h>
using namespace std;
int a[1001][1001];
int main() {
	int n = 0;
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j <= i; j++)
			cin >> f[i][j];
	for (int i = n - 2; i >= 0; i--)
		for (int j = 0; j <= i; j++)
			f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);
	cout << f[0][0];
}

方法三:記憶化搜索

我們畫出來方法一的搜索樹:

用紅色圈起來的地方顯然是重覆計算了,可以用一個數組來記錄搜過的狀態,如果再次搜到已搜過的狀態,就直接返回記錄的值,這樣沒有了重覆搜索,時間複雜度是 \(\Theta(n^2)\).

memset(f, -1, sizeof(f));
int solve(int i, int j) {
    if (f[i][j] >= 0) return f[i][j];
    return f[i][j] = a[i][j] + (i == n ? 0 : 
                                max(solve(i + 1, j), solve(i + 1, j + 1)));
}


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 我在整理Hive的存儲格式和壓縮格式,本來打算一篇發出來,結果其中一小節就有很多內容,於是打算寫成Hive存儲格式和壓縮格式系列。 本節主要講一下Hive存儲格式最早的典型的列式存儲格式RCFile。 綜述 RCFile(Record Columnar File)文件格式是FaceBook開源的一種 ...
  • 1 環境搭建 搭建JavaScript開發環境有很多種組合,本文中採用Visual Studio Code和Node.js的組合,詳細如下所示: 1.1 Node.js環境搭建 1.1.1 下載Node.js 不管是基於Windows還是Linux,都需要下載相應的安裝包,到Node.js官網根據系 ...
  • 文章已收錄到我的 GitHub 中,歡迎 star cookie 是什麼和使用場景 cookie 是伺服器端保存在瀏覽器的一小段文本信息,瀏覽器每次向伺服器端發出請求,都會附帶上這段信息(不是所有都帶上,具體的下文會介紹)。 使用場景: 對話管理:保存登錄、購物車等需要記錄的信息 個性化:保存用戶的 ...
  • 前言 開發項目中,使用到 Eruda 列印控制台信息顯示 文檔:https://github.com/liriliri/eruda 安裝 Eruda npm install eruda --save 引入 import eruda from "eruda"; 常使用方法 顯示 eruda.show( ...
  • 目錄 一.簡介 二.效果演示 三.源碼下載 四.猜你喜歡 零基礎 OpenGL (ES) 學習路線推薦 : OpenGL (ES) 學習目錄 >> OpenGL ES 基礎 零基礎 OpenGL (ES) 學習路線推薦 : OpenGL (ES) 學習目錄 >> OpenGL ES 轉場 零基礎 O ...
  • 1.什麼是自定義分頁器 當我們需要在前端頁面展示的數據太多的時候,我們總不能將數據展示在一頁上面吧!這時,我們就需要自定義一個分頁器,將數據分成特定的頁數進行展示,每一頁展示固定條數的數據! 2.為什麼要用自定義分頁器 如上所說:為了將數據分成多頁進行展示,分別閱讀,方便查詢! 3.如何使用自定義分 ...
  • django-rest-framework開發api介面 (1) 創建django項目drfdemo1並且創建一個名為app的應用 django-admin startproject drfdemo1 python manage.py startapp app (2) 安裝django-rest-f ...
  • 1、導入模塊 import requests import csv from concurrent.futures import ThreadPoolExecutor 2、先獲取第一個頁面的內容 分析得到該頁面的數據是從getPriceData.html頁面獲取,並保存在csv文件中 得到url地址 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...