算法合集之減少冗余與算法優(yōu)化(編輯修改稿)
2024-11-14 18:36 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 未知點(diǎn) 處理中的點(diǎn) 已知點(diǎn) 不必求出的點(diǎn) [ , ]Fi j[ , 1]?F i j[ 2 , ]? jF i j空間復(fù)雜度： O(log2N) 例 1：整數(shù)拆分 —— 減少冗余 J I 1 2 3 0 1 2 3 4 5 6 7 8 當(dāng) N≠2M時(shí)， 可轉(zhuǎn)化成 N=2M的形式求解 例 1：整數(shù)拆分 —— 減少冗余 設(shè) N=2Mr (2M1N2M) 0 0 0 0 0 0 0 r 目標(biāo) F[N,M1] F[N,M] 例 1：整數(shù)拆分 —— 小結(jié) 冗余 時(shí)空復(fù)雜度較高 去除冗余后 時(shí)空復(fù)雜度相對(duì)很低 去除冗余 優(yōu)化本題的關(guān)鍵 例 1：整數(shù)拆分 —— 最后的思考 更優(yōu)秀的算法？ Exploring 公式？ . . . 例 2：最大獎(jiǎng)品價(jià)值 —— 問(wèn)題描述 有 N+2級(jí)樓梯 ， 分別用 0至 N+1編號(hào) ， 第 1至N級(jí)樓梯上每級(jí)都放有一個(gè)獎(jiǎng)品 ， 每個(gè)獎(jiǎng)品都有一個(gè)正的價(jià)值 。 如果某人從第 0級(jí)開(kāi)始 ， 向上走M(jìn)步正好到達(dá)第 N+1級(jí)樓梯 ， 他將得到所走過(guò)的樓梯上的所有獎(jiǎng)品 ， 否則他將一無(wú)所獲 。 問(wèn)能得到的獎(jiǎng)品價(jià)值的和最大是多少 ？ 當(dāng)然 ， 一步不可能走太多級(jí)樓梯 ， 假設(shè)每步最多上 K級(jí) ， 即最多從第 i 級(jí)走到第 i+K 級(jí) 。 例 2：最大獎(jiǎng)品價(jià)值 —— 數(shù)學(xué)模型 有一列數(shù) a0, a1, a2, … , aN, aN+1 其中 a0=0 a1,a2,a3, …
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1