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