动态编程基础——第 2 部分（动态编程是什么）

myzbx 2025-07-03 18:17 28 浏览

有两种方法可以使用动态规划来解决问题。在这篇文章中，我们将了解制表法。请参阅我的动态编程基础——第 1 部分了解记忆方法。

记忆
制表

什么是动态规划？

它是一种简单递归的优化技术。它大大减少了解决给定输入问题的时间。它将问题分解为嵌套的子问题并计算这些子问题的结果。这些子问题的结果被重用以避免重新计算。它将问题的时间复杂度从指数降低到多项式。这种重用子问题的结果可以通过两种方式完成——记忆和制表。

什么是制表？

具有确定大小的数据结构根据要求使用默认值进行初始化，并且仅迭代一次以计算最终结果。在迭代结束时，可以检索输出。

有制表：

问题陈述：以下函数有两个参数——targetSum 和一个整数元素数组，如果数组元素的任何组合可以求和到 targetSum，则返回 true。该组合可以是数组中的任意数量，考虑任意次数。

例如，targetSum:3 , arr:Array(1,4,7) => returns true => 1+1+1=3

附表代码说明：

例如，table(7,Array(5,4,3))

使用默认值初始化数组：

0 对于任何情况都是正确的，因为 targetSum 0 对于任何组合都是可能的。

迭代数组中的每个元素以更新值：

对于索引 0：

对于索引 1：

对于索引 2：

对于索引 3：

对于索引 4：

对于索引 5：

对于索引 6：

对于索引 7：

数组使用值更新，带有 T 的数组表示它们的索引可能与数组中的一个或多个元素组合（总和）一起使用。最终值数组（targetSum），即我们示例中的 arr(7)，返回结果。

def table(targetSum: Int, arr: Array[Int]):Boolean={
 val tbl: Array[Boolean]=Array.ofDim(targetSum+1)
 tbl(0)=true
 var i=0
 while(i<=targetSum){
 if(tbl(i)==true){
 arr.foreach(j=>{if (i+j <= targetSum) tbl(i+j)=true})
 }
 i=i+1
 }
 tbl(targetSum)
}table(7,Array(9,10,7))
table(300,Array(7,14))

结论：

通过使用制表，我们减少了运行时间。它有助于加快执行速度并避免内存不足错误。

JS 数组迭代

上一篇：Lambda 函数，你真的的了解吗（lambda函数用法）
下一篇：JDK21新特性:Sequenced Collections

动态编程基础——第 2 部分（动态编程是什么）

相关推荐

使用VSCode模板提高Vue开发效率（vscode开发vue3）

吃透 Vue 项目开发实践|16个方面深入前端工程化开发技巧【下】

8.7k star，一款超炫酷的动态可视化大屏项目

说下你的vue项目的目录结构，该怎么划分?

这么牛逼的cursor功能，赶紧用起来

移动前端重构实战系列:5-7章（前端移动端主要技术有哪些）

用上Vue3，你真的变了吗?（vue3 key）

20个免费音乐音效下载网站，无版权素材商业影片也可用

comfyui安装MimicMotion扩展，AI跳舞动作模仿

什么是“恒定光圈”，什么是“浮动光圈”?-摄影早自习第331