一起刷算法_动态规划01

摘要:本周我利用休息时间刷了两道简单、一道中等的动态规划算法题目,和大家一起分享一下,作为动态规划算法专题的开始。

我的主页 https://qupzhi.com ,转载请注明出处。

  • 以下内容用go语言实现

动态规划三要素

三要素

  1. 最优子结构性质,通俗的说法就是问题的最优解包含其子问题的最优解
  2. 边界
  3. 状态转移方程

重复求区间和

1
2
3
4
5
6
7
8
9
10
11
12
13
给定一个整数数组  nums,求出数组从索引 i 到 j  (i ≤ j) 范围内元素的总和,包含 i,  j 两点。

示例:

给定 nums = [-2, 0, 3, -5, 2, -1],求和函数为 sumRange()

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
说明:

你可以假设数组不可变。
会多次调用 sumRange 方法。

三种思路:

  1. 直接根据每次传进来的区间进行现场计算
  2. 用一个Map,把每次传进来的区间拼成一个key,二次查询的时候就有了缓存
  3. 直接用一个1D的数组,每个元素存0到当前值之间的和,这样区间和就是两个下标存元素相减就可以了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

type NumArray struct {
}
var sum *[]int
func Constructor(nums []int) NumArray {
var obj NumArray
for k, v := range nums {
if k > 0 {
nums[k] = nums[k-1] + v
}
}
sum = &nums
return obj
}

func (this *NumArray) SumRange(i int, j int) int {
if i == 0 {
return (*sum)[j]
}
return (*sum)[j] - (*sum)[i-1]
}


func Test(){
arr := []int{1,2,3,4}
obj := Constructor(arr)
res := obj.SumRange(0,3)
fmt.Println(res)
}

经典问题爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数。

示例 1:

输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2:

输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

因为每次都可以分解为1步和2步,边界就是1步2步,状态转移方程就是f(n) = f(n-1) + f(n-2) (n>=3),这里提供三种思路

  1. 递归
  2. 字典
  3. 动态规划,每次都用前一次的值推倒后一次的答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

// f(n) = f(n-1) + f(n-2) (n>=3)
// f(1) = 1
// f(2) = 2
// 方法一、递归
func climbStairs1(n int)int{
if n < 0 {
return 0
}
if n == 1 {
return 1
}
if n == 2 {
return 2
}
return climbStairs1(n-1) + climbStairs1(n-2)
}

//方法二、动归
func climbStairs(n int) int {
if n == 1 {
return 1
}
if n == 2 {
return 2
}
res,a,b := 0,1 ,2

for i:=3;i<=n;i++{
res = a + b
a = b
b = res
}
return res
}

func Test1(){
fmt.Println(climbStairs1(10))
}
func Test2(){
fmt.Println(climbStairs(100))
}

最大正方形面积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
221. Maximal Square
Medium

1165

29

Favorite

Share
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:

Input:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

三种思路:

  1. 方法一 逐渐增加连续的 ‘1’ 的长度 ,然后用一个函数去看是否构成正方形,构成的话就继续增加边长,直到找到最大的正方形为止
    时间复杂 O((mn)^2) 空间 O(1)

  2. 方法二 用一个二维数组的的每个元素都来保存边长
    每次只要遍历到的点是1,就开始取他的上、左、左上三个值取最小,再加1得到当前点的值

    1
    2
    dp[x,y] = min(min(dp[x-1][y],dp[x][y-1]) , dp[x-1][y-1])+1
    O(mn) O(mn)
  3. 方法三

    1
    2
    3
    4
    5
    input [1,1,0][1,1,0]

    0000
    0110
    0120
  • 每次遍历总是要知道上一行的数据,所以至少得保留一行
  • 可以发现,遍历到第三行的时候,第一行已经没有用了!
  • 每次遍历的时候,假设只保留上一行,比如在第三行,每次走一位,我们要更新当前值,当前位置的马上的覆盖值对于下一次来说就是左上角的值(2*2)
  • 对于这一次来说就是上,因为当前位置的左边已经更新了所以就是左,那我们当前就出现了左、上、左上三个值了,凑够了。
  • 初始化就全0,prev=0
    1
    2
    dp[y]=min(dp[y-1],dp[y],prev)
    O(mn) O(m)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// 方法二
func maximalSquare(matrix [][]byte) int {
rows := len(matrix)
cols := 0
if rows>0{
cols = len(matrix[0])
}else{
cols = 0
}
dp := make([][]int,rows+1)
for i:=0;i < len(dp);i++{
dp[i] = make([]int,cols+1)
}
maxlen := 0
for x:=1;x <= rows; x++{
for y:=1;y <= cols;y++{
if matrix[x-1][y-1] == '1'{
tmp := min(min(dp[x-1][y],dp[x][y-1]),dp[x-1][y-1])+1
dp[x][y]=tmp
maxlen = max(maxlen,tmp)
}
}
}
return maxlen * maxlen
}

// 方法三
func maximalSquare2(matrix [][]byte) int {
rows := len(matrix)
cols := 0
if rows>0{
cols = len(matrix[0])
}else{
cols = 0
}
dp := make([]int,cols +1)
maxlen,prev := 0,0
for x:=1;x <= rows; x++{
for y:=1;y <= cols;y++{
tmp := dp[y] //当前值当下一次的prev
if matrix[x-1][y-1] == '1'{
dp[y] = min(min(dp[y],dp[y-1]),prev) + 1 //分别对应上,左,左上
maxlen = max(dp[y],maxlen)
}else{
dp[y] = 0
}
prev = tmp
}
}
return maxlen * maxlen
}
func Test1(){
t1 :=[][]byte{{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}}
t2 :=[][]byte{}
fmt.Println(maximalSquare(t2))
fmt.Println(maximalSquare2(t1))
}

func min(x, y int) int {
if x < y {
return x
}
return y
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
坚持原创技术分享,您的支持将鼓励我继续创作!