2022年9月

【算法随笔】剪枝

1 条评论 默认分类 笔记 算法 MisakaStone
剪枝是一种可以提高搜索算法时间和空间效率的技巧，经过剪枝或其他策略优化过的算法在执行效率上远超一般未经剪枝的算法。例1 数的划分题目来源：P1025 NOIP2001 提高组 数的划分 - 洛谷题目描述将整数 $n$ 分成 $k$ 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。例如：$n=7$，$k=3$，下面三种分法被认为是相同的。$1,1,5$; $1,5,1$; $5,...

【算法随笔】动态规划

0 条评论 默认分类 笔记 算法 MisakaStone
动态规划（Dynamic Programming）是计算机中解决最优化问题的一种方法，具有效率高、速度快的优点。引入一个经典的动态规划问题：给定一个无序的数组，求出最长的递增子序列的长度。例如，在 $ nums = [1,5,2,4,3] $ 中，最长子序列为 $ [1,2,3] $，长度为3。首先采用深搜来解决，代码如下：public static int dfs(int[] nums, ...

【算法随笔】记忆化搜索

0 条评论 默认分类 笔记 算法 MisakaStone
记忆化搜索可以减少重复计算。以斐波那契数列为例，简单的递归函数存在大量重复计算，时间复杂度较高，因此可以采用记忆化搜索的算法来提高计算效率。$ F(0)=1 $ $ F(1)=1 $$ F(2)=F(1)+F(0) $$ F(3)=F(2)+F(1) $$ ... $$ F(n)=F(n-1)+F(n-2) $ 代码如下Scanner keyboard = new Scanner(Syste...