package cap3

// Work9 蚂蚁爬房，求a~b路线数，动规解法，时间O(n)，空间O(1)
func Work9(a, b int) int {
    if a > b {
        return 0
    }

    length := b - a
    if length <= 2 {
        return 1
    }

    // 从a开始到后两个房间路线分别有一个和两种路线
    //a+1:（a->a+1），a+2：（a->a+1->a+2, a->a+2）
    prev, prev2 := 1, 2
    step := 0
    // 前两步已经走过了，所以len-2
    for i := 0; i < length-2; i++ {
        step = prev + prev2

        // 上两个变成上一个，上一个变成下一个
        prev2 = prev
        prev = step
    }

    return step
}