Dynamic Programming (动态规划)

动态规划思想,是用已知的规律,从历史数据计算出未来的最优解,这种方法省去暴力算法中的不必要的样本空间,非常重要。

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

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

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

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

1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶  
提示:
1 <= n <= 45
解题思路

N级台阶的解来自之前N-1级台阶的各自解之和,可以尝试创建动态规划的转移方程。首先尝试罗列出部分基础数值:

f(0)=1    //也可以不考虑0的情况,因为题目说了n>=1,这样的话,程序就应该从f[1]+f[2]开始
f(1)=1
f(2)=1+1=2  //全部一级级走(1)+ 只走2级(1)
f(3)=1+1+1=3  //全部一级级走(1)+ 先2次一级再2级1次(1)+ 先2级1次再1级1次(1)
f(4)=1+1+1+1+1=5  //全部一级级走(1)+ 先2次一级再2级2次(1)+ 先3次一级再2级1次(1) + 先2级1次再1级2次(1)+ 先2级1次再2级1次(1)
...

f(4)已经可以看出一些规律,它的结果是从f(3)+f(2)合并而来的,当然为了确保正确,可以继续抽样尝试下去,保证不是因为f(3)+x这种情况。

到此我们可以写出方程:

f(n) = f(n-1) + f(n-2)

体现在数组slice/array中就是[]int中的第n个值等于之前n-1n-2上的值之和。

题解

Using extra array space:

func climb(n int) int {
	if n <= 1 {
		return n
	}
	dp := make([]int, n+1)
	dp[0] = 1
	dp[1] = 1
	for i := 2; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
		fmt.Println(dp)
	}
	//fmt.Println(dp)
	return dp[n]
}

Optimized best solution:

func climbStairs(n int) int {
    p, q, r := 0, 0, 1	//p是前前值,q是前值,r是当下值,使用从i(n)从1开始的话,之前的状态都应该是0,这样当i等于3的时候就会和上面使用数组的程序有相同结果
    for i := 1; i <= n; i++ {
        p = q
        q = r
        r = p + q
    }
    return r
}

比特位计数(数组元素间的关系)

给你一个整数 n ,对于 0 <= i <= n 中的每个 i ,计算其二进制表示中 1 的个数 ,返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1:

输入:n = 2
输出:[0,1,1]
解释:
0 --> 0
1 --> 1
2 --> 10
示例 2:

输入:n = 5
输出:[0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

提示:

0 <= n <= 105
解题思路

先尝试列出适量的数值,并尝试找出规律。

输入:n = 16
输出:   [0,1,1,2,1,2,2,3,1,2,2, 3, 2, 3, 3, 4, 1]
数组下标 [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
6 --> 110
7 --> 111
8 --> 1000
9 --> 1001
10 --> 1010
11 --> 1011
12 --> 1100
13 --> 1101
14 --> 1110
15 --> 1111
16 --> 10000

自己观察和尝试,会发现其实是有规律的:

  • 2-3的二进制数字是0-1的二进制数字基础上在数组最前面多一个15-7的二进制数字是0-3的二进制数字基础上在数组最前面多一个1,比如6110210前面多17111311前面多19-15是把之前0-7的对应数组最前面加1。所以只要把当前n向前数前一次2整数幂就可以了,比如要找10,则之前一次2整数幂已经到8了,10对应的应该就是10-8=2之前加1
  • 这里面只有当n2整数幂时才有一点点差别,这些数字都是最前面为1之后全是0。这种规律的结果,在最后输出数1的个数中就体现为后一段2整数幂区间比前一段2整数幂各自数组中1的个数多1。

所以可以提取出规划公式f(n)=f(n-2**i)+1,其中i是升幂次数,f(n)是当前对应二进制中1的个数。所以接下来如何找到正确的i就是关键。 上面提到的一个2整数幂的规律是头1后全0,如果把它与前一位的数字进行与操作(&),即如果相同位上有相同数字,则返回1,否则返回0。因为2整数幂的二进制是在新的最前面多1,之后全是0,一旦与之前的数进行&操作,必然返回0

题解

highBit即为临近的最高2整数幂。这里正好数组下标和整数的二进制相对应,这样就不用拆分输入n入数组了。

func countBits(n int) []int {
    bits := make([]int, n+1) //n+1可从上面的输出例子中找出规律
    highBit := 0
    for i := 1; i <= n; i++ {
        if i&(i-1) == 0 {
            highBit = i
        }
        bits[i] = bits[i-highBit] + 1
    }
    return bits
}

使用最小花费爬楼梯

给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1:

输入:cost = [10,15,20]
输出:15
解释:你将从下标为 1 的台阶开始。
- 支付 15 ,向上爬两个台阶,到达楼梯顶部。
总花费为 15 。
示例 2:

输入:cost = [1,100,1,1,1,100,1,1,100,1]
输出:6
解释:你将从下标为 0 的台阶开始。
- 支付 1 ,向上爬两个台阶,到达下标为 2 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 4 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 6 的台阶。
- 支付 1 ,向上爬一个台阶,到达下标为 7 的台阶。
- 支付 1 ,向上爬两个台阶,到达下标为 9 的台阶。
- 支付 1 ,向上爬一个台阶,到达楼梯顶部。
总花费为 6 。

提示:

2 <= cost.length <= 1000
0 <= cost[i] <= 999
解题思路

比较容易想到的是下面这个错误的解题思路:

func minCostClimbingStairs(cost []int) int {
    var c int
    for i := 2; i <= len(cost);  {
        x:=cost[0]
        y:=cost[1]
        if y<=x {
            c+=y
            cost=cost[2:]
        } else {
            c+=x
            cost=cost[1:]
        }
    }
    return c
}

这是错误的,为什么呢?因为它每一次判断都只关心自己脚下的路,没有看走来的路。它每次都选了自己当下认为最棒的选择,但是每次做这种2选1的选择的时候,都是放弃了另一个,而下一次再选择的时候,如果没有充分知道之前所有可能的结果,就会得到偏离的错误结果。这种情况类似于判断时只选择了一层逻辑,那就是之前认为最好的路,可是之前认为最好的路有可能并不是最佳路径,比如[10,15,20],如果只关心脚下,那么应该是选择10和15,最后会总cost25,可实际上如果在最顶的角度往回看,之前走15才是最佳的。

题解

那么正确的方法是什么呢?我们要把所有节点的可能结果都记录下来,让后一次选择时都知道前面有什么可能,这样就能做出正确判断了:

func minCostClimbingStairs(cost []int) int {
    n := len(cost)
    dp := make([]int, n+1)
    for i := 2; i <= n; i++ {
        fmt.Printf("i=%v,dp[i-1]=%v,cost[i-1]=%v\n",i-1,dp[i-1],cost[i-1])
        fmt.Printf("i=%v,dp[i-2]=%v,cost[i-2]=%v\n",i-2,dp[i-2],cost[i-2])        
        dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
    }
    return dp[n]
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

把给出的数组cost对应的走每一位可能的总消耗都存入数组dp,这样下一次选择的时候就可以看之前的数据了。这样才是真正的动态思想。这里i<=n dp := make([]int, n+1)这个思想非常重要,它考虑了站上顶意味着要比输入cost []int多一位。