Sutdown Blog

「行至朝雾里，坠入暮云间」

算法专题：回溯和分支定界

[TOC] 前言：解决问题的时候，可以列出所有的候选解，然后依次检查每一个，检查完后就可以得到所需要的解。对候选解进行系统检查的常用两种方法是回溯和分支定界。推荐文章：回溯法算法复习伪码—自用-CSDN博客回溯： 1.定义：回溯是一种系统的搜索问题解答的方法。首先定义一个解空间，下一步组织解空间以便于它能容易的被搜索（树或者图），然后再按照深度优先的方法进行搜索。...

Posted by Sutdown on March 28, 2023

算法专题：分治法（Divide and Conquer）

[TOC] 一：分治法概述分治法思想分治法的基本思想是将问题分成（divide）多个子问题，再递归（Conquer）的解决每个子问题，再将子问题的解合并（Combine）成原问题的解。 1）这个思想是不是很熟悉，第一反应能不能想到归并排序和快速排序。后面我们会对两种排序和分治法的思想进行具体分析。 2）分成多个子问题，有没有想到动态规划和贪心法，它们有什么区别呢？看一下这三...

Posted by Sutdown on March 20, 2023

算法专题：动态规划（Dynamic Programming）

一：前言学习基础：数据结构与算法。文章中少部分涉及数据结构的知识不作讲解。使用情况：在动态规划中，一个问题必须拥有重叠子问题和最优子结构，才能用动态规划解决。重叠子问题：一个问题可以被分解为若干个子问题，且这些子问题会重复出现。比如求斐波那契数列时，递归（自顶而下Top-down Approach）会产生大量重叠子问题，此时可以采用记忆化搜索记住那些重叠子问题，避免多次计算从...

Posted by Sutdown on March 12, 2023