2020年12月

算法导论-动态规划-笔记

动态规划:找其中一个最优解
4个步骤来设计
1.刻画一个最优解的结构特征
2.递归地定义最优解的值
3.计算最优解的值,通常是自底向上的方法
4.构造解

适合用动态规划求解的最优化问题,应具备两个要素:
最优子结构、子问题重叠

对于不同问题领域,最优子结构的不同 体现在两个方面:

  1. 原问题的最优解中涉及多少个子问题
  2. 在确定最优解使用哪些子问题时,我们需要考察多少种选择

动态规划 vs 贪心算法
能够应用贪心算法的问题也必须具有最优子结构性质。两者不同之处是:
动态规划,首先寻找子问题的最优解,然后在其中选择
贪心算法,首先做一次“贪心”选择————在当时(局部)看来最优的选择————然后求解选出的子问题,从而不必求解所有可能相关的子问题

贪心算法两个关键要素:
贪心选择性质
最优子结构

GO SQL MySQL driver解读

GO标准库中的database/sql搭配社区开源的mysql驱动go-sql-driver/mysql,是我们常用的组合。

标准库实现了什么

Package sql provides a generic interface around SQL (or SQL-like) databases.
抽象了统一的连接、读写、事务等操作,负责调用实际的driver与特定的数据库交互(比如MySQL、SQLlite、Oracle等)
database/sql库维护了数据库连接池,它并发安全,可供多个协程并发调用。

driver实现了什么

与具体的数据库的交互过程

怎么用

用户代码直接调用标准库,同时指明使用哪个driver,使用之前要先注册driver

import (
"database/sql"
"time"

_ "github.com/go-sql-driver/mysql"
)

// ...
db, err := sql.Open("mysql", "user:password@/dbname")
if err != nil {
    panic(err)
}
// See "Important settings" section.
db.SetConnMaxLifetime(time.Minute * 3)
db.SetMaxOpenConns(10)
db.SetMaxIdleConns(10)