前言

作為API Call，可以不去學(xué)算法，但是高級工程師，不可能對算法一無所知。

上一篇斐波拉契數(shù)列的問題，講述了動(dòng)態(tài)規(guī)劃算法的大概套路，這次來一點(diǎn)真正的實(shí)戰(zhàn)，編程語言依然用kotlin.

前文回顧

上一篇文末說的動(dòng)態(tài)規(guī)劃基本套路，最重要的，也是第一個(gè)步驟是寫出動(dòng)態(tài)規(guī)劃"狀態(tài)轉(zhuǎn)移方程"

這一步驟是和編程語言完全無關(guān)的。純粹的數(shù)學(xué)理論。

動(dòng)態(tài)規(guī)劃實(shí)戰(zhàn)：理想版湊零錢問題

問題拋出

一件商品要18塊，但是我只有零錢，1元，2元，5元，假設(shè)零錢數(shù)目無限多?，F(xiàn)在我要知道，我要用零錢買這一件商品，所需的零錢的最少張數(shù)是多少。

問題分離

前提

零錢有1元，2元，5元, 并且數(shù)量無限多。

目標(biāo)

求解湊出18元的目標(biāo)金額所需零錢的最少張數(shù)

問題分解

分情況討論，

如果目標(biāo)金額是0，那么不需要任何零錢來湊，所以零錢張數(shù)是0
如果目標(biāo)金額是負(fù)數(shù)，這屬于異常情況，我零錢張數(shù)返回-1，表示異常情況。
如果目標(biāo)金額是正數(shù)，那么要嘗試用零錢去湊，窮舉列出所有可以達(dá)成這個(gè)目標(biāo)的零錢組合，然后取最小值。

具體做法為：遍歷所有零錢，計(jì)算出目標(biāo)金額與當(dāng)前零錢面值的差，把差進(jìn)入下一輪循環(huán)。本輪循環(huán)取1+遞歸回調(diào)值的最小值。

看著有點(diǎn)繞，寫成“狀態(tài)轉(zhuǎn)移方程”一眼就能看明白.

image-20200502132911765.png

根據(jù)上面的“狀態(tài)轉(zhuǎn)移方程”，寫出偽代碼：

  val coins = [1,2,5]// 零錢只提供1,2,5元的，不限數(shù)目
  res = Long.maxvalue.// 由于是要取最小值，所以初始化為long的最大值
  f(n) = if(n=0) return 0 (目標(biāo)金額是0，那就不需要湊，返回0)
         if(n<0) return -1(目標(biāo)金額是負(fù)數(shù)，異常情況，返回-1)
         if(n>0) {
            for(i in coins){// 遍歷所有零錢 
               res = min(res,1+ f(n-coin)) // 用一張當(dāng)前零錢面值，加上扣除當(dāng)前面值之后的金額遞歸回調(diào)
            }
            return res
      }

先不寫程序代碼，我們來分析一下這種原始解法的復(fù)雜度。

這里我們先把零錢數(shù)組的size設(shè)定為k

時(shí)間復(fù)雜度:

子問題的個(gè)數(shù)是

這里不止涉及到了遞歸，還涉及到了遍歷size為k數(shù)組的，就這個(gè)問題而言,按照最壞的情況來算，假設(shè)每一個(gè)子問題都會(huì)分裂k份，那么所有子問題的個(gè)數(shù)就是kⁿ
解決一個(gè)子問題所需的時(shí)間

size為k的循環(huán)中，存在一次加法，和一次min對比計(jì)算，所以滿打滿算有2k=2k*次運(yùn)算.

所以，時(shí)間復(fù)雜度就是kⁿx2k = O(2kⁿ⁺¹)*

一個(gè)指數(shù)級別的時(shí)間復(fù)雜度，一看就有點(diǎn)慎得慌。

空間復(fù)雜度：

由于沒有數(shù)據(jù)保存，一律認(rèn)為空間復(fù)雜度是O(1)

暴力解法

OK，思路清楚了，我們開始碼代碼

import java.lang.Integer.min

val change = arrayOf(1, 2, 5) // 零錢就是1,2,5

var calCount = 0

/**
 * @param targetAmount 要用零錢湊成的目標(biāo)金額
 */
fun changeMoney(targetAmount: Long): Int {
    var finalCount = Int.MAX_VALUE // 由于要計(jì)算出最小值，所以先初始化為最大值
    if (targetAmount == 0L) return 0 // 賊
    if (targetAmount < 0) return -1
    for (c in change) {
        val subRes = changeMoney(targetAmount - c)
        if (subRes == -1) continue
        finalCount = min(finalCount, 1 + subRes)
    }
    calCount++
    return finalCount
}

fun main() {
    val start = System.currentTimeMillis()
    val changeMoney = changeMoney(18)
    println("湊成目標(biāo)金額所需的最小零錢數(shù)：$changeMoney , 子問題總數(shù)是${calCount}")
    println("耗時(shí)：${System.currentTimeMillis() - start}ms")
}

執(zhí)行結(jié)果：

湊成目標(biāo)金額所需的最小零錢數(shù)：5 , 子問題總數(shù)是12956
耗時(shí)：4ms

心算一下，18塊錢，拆分成(1,2,5)零錢，應(yīng)該是需要3x5+2x1+1x1 , 所以零錢的張數(shù)是 3+1+1 = 5. 可以看到，僅僅是很小的金額的計(jì)算，這種窮舉的暴力解法，居然要將近1萬3千次運(yùn)算?？上攵渲杏卸嗌偈菬o用功。

一重改進(jìn)

既然是無用功，那么使用map保存已經(jīng)計(jì)算出的結(jié)果，再次求值時(shí)，不必重新計(jì)算，而是直接取值。

import java.lang.Integer.min

val change = arrayOf(1, 2, 5) // 零錢就是1,2,5

var calCount = 0

/**
 * 優(yōu)化方案1:用一個(gè)容器把已經(jīng)計(jì)算出來的結(jié)果保存起來,計(jì)算之前先看容器中有沒有,有就直接取，沒有就去計(jì)算，計(jì)算之后存入容器
 * @param targetAmount 要用零錢湊成的目標(biāo)金額
 * 進(jìn)行if return/continue 優(yōu)化
 */
fun changeMoney2(map: HashMap<Long, Int>?, targetAmount: Long): Int {
    val mapThis = map ?: HashMap()// 如果是空，就創(chuàng)建

    var finalCount = Int.MAX_VALUE // 由于要計(jì)算出最小值，所以先初始化為最大值
    if (targetAmount == 0L) return 0
    if (targetAmount < 0) return -1
    for (c in change) {
        //要不要執(zhí)行？先看容器里面有沒有
        var cache = mapThis[targetAmount - c]
        if (cache == null) {// 如果找不到，就說明容器中沒有
            cache = changeMoney2(mapThis, targetAmount - c)// 那就計(jì)算
            if (cache == -1) continue // -1異常情況就不要參與保存了
            mapThis[targetAmount - c] = cache // 保存
        }
        finalCount = min(finalCount, 1 + cache)// 最終結(jié)果記得+1,同時(shí)取最小值
        calCount++
    }

    println("計(jì)算過程：$finalCount  $mapThis")
    return finalCount
}

fun main() {
    val start = System.currentTimeMillis()
    val changeMoney = changeMoney2(null, 18)
    println("湊成目標(biāo)金額所需的最小零錢數(shù)：$changeMoney , 子問題的總運(yùn)算次數(shù)是：${calCount}")
    println("耗時(shí)：${System.currentTimeMillis() - start}ms")
}

執(zhí)行結(jié)果：

計(jì)算過程：5  {0=0, 1=1, 2=1, 3=2, 4=2, 5=1, 6=2, 7=2, 8=3, 9=3, 10=2, 11=3, 12=3, 13=4, 14=4, 15=3, 16=4, 17=4}
湊成目標(biāo)金額所需的最小零錢數(shù)：5 , 子問題的總運(yùn)算次數(shù)是：49
耗時(shí)：5ms

子問題的運(yùn)算次數(shù)，從之前的上萬次，直接降低為18次。

但是運(yùn)行耗時(shí)幾乎沒有變化。這是由于目標(biāo)數(shù)值太少，僅僅是18，還不足以看出算法耗時(shí)的差別。換成158,1588試試看

零錢依然假定為k種

時(shí)間復(fù)雜度：

子問題的個(gè)數(shù)：

目標(biāo)金額不會(huì)超過總金額數(shù)(加入目標(biāo)金額是n=100，最多也就循環(huán)100次)，所以取最大值 n
子問題解決消耗時(shí)間:

每一個(gè)子問題只需要一次加法，和一次min計(jì)算，但是必須循環(huán) k 次，所以每個(gè)子問題耗時(shí) 2k

時(shí)間復(fù)雜度降低為O(2kn), 直接從之前的k的指數(shù)級別，降低為k的1次方。運(yùn)算次數(shù)驟減。

空間復(fù)雜度：

子問題的個(gè)數(shù)：

n
子問題解決消耗空間:

每一個(gè)子問題都會(huì)在map中保存一個(gè)值，所以每個(gè)子問題消耗空間1

即使子問題的個(gè)數(shù)是n，但是由于共享hashmap的原因，空間復(fù)雜度是 O(n)

二重改進(jìn)

把從上而下的逆向遞歸，改成更容易理解的從下而上的遍歷。先計(jì)算出f(1),f(2)...最后計(jì)算到最終值f(18).

import java.lang.Integer.min

val change = arrayOf(1, 2, 5) // 零錢就是1,2,5

var calCount = 0

fun changeMoney3(lastTarget: Int): Int {
    // 所以做法就是，從0開始往后推演，從樹根往樹頂推算
    val hashMap = HashMap<Int, Int>()
    var result = -1
    for (currentTarget in 1..lastTarget) {
        result = getMin(currentTarget, hashMap)
    }
    println("最終保存的map內(nèi)容是：$hashMap ")
    return result
}

fun getMin(currentTarget: Int, map: HashMap<Int, Int>): Int {
    if (map.containsKey(currentTarget)) {
        println("找到已經(jīng)存在的記錄: map[${currentTarget}]=${map[currentTarget]!!}")
        return map[currentTarget]!!
    }
    var res = Int.MAX_VALUE
    loop@ for (c in change) {
        val currentRes = when {
            currentTarget - c == 0 -> {
                map[currentTarget] = 1
                1
            }
            currentTarget - c > 0 -> {
                val x = 1 + getMin(
                    currentTarget - c,
                    map
                )/* 1表示當(dāng)前金額,getMin(currentTarget - c, map) 表示去掉當(dāng)前金額之后，所需零錢數(shù) */
                calCount++
                map[currentTarget] = x // 保存起來
                x
            }
            else -> {
                continue@loop
            }
        }
        res = min(res, currentRes)
    }

    return res
}

//測試代碼
fun main() {
    val start = System.currentTimeMillis()
    val changeMoney3 = changeMoney3(18)
    println("湊成目標(biāo)金額所需的最小零錢數(shù)：$changeMoney3 子問題運(yùn)算次數(shù)為：${calCount}")
    println("耗時(shí)：${System.currentTimeMillis() - start}ms")
}

運(yùn)行結(jié)果：

最終保存的map內(nèi)容是：{1=1, 2=1, 3=2, 4=2, 5=1, 6=2, 7=2, 8=3, 9=3, 10=2, 11=3, 12=3, 13=4, 14=4, 15=3, 16=4, 17=4, 18=5} 
湊成目標(biāo)金額所需的最小零錢數(shù)：5 子問題運(yùn)算次數(shù)為：46
耗時(shí)：5ms

零錢數(shù)依然設(shè)定為K

時(shí)間復(fù)雜度：

子問題的個(gè)數(shù)：

目標(biāo)金額是n，最多進(jìn)行n次遍歷，所以子問題的個(gè)數(shù)是 n
子問題解決消耗時(shí)間:

一個(gè)子問題，依然是一次加法和一次min運(yùn)算，再算上外層k消耗時(shí)間為2

時(shí)間復(fù)雜度降低為O(2kn)

空間復(fù)雜度：

子問題的個(gè)數(shù)：

n
子問題解決消耗空間:

每一個(gè)子問題都會(huì)在map中保存一個(gè)值，所以每個(gè)子問題消耗空間1

即使子問題的個(gè)數(shù)是n，但是由于共享hashmap的原因，空間復(fù)雜度是 O(n)

復(fù)雜度和上面一種解法一樣！但是思維上，比上一種更容易理解，更人性化。

三重改進(jìn)

之前我是用map來保存前一步計(jì)算出的值，嘗試一下能否不用map，而只是用循環(huán)內(nèi)的臨時(shí)變量來存。

但是發(fā)現(xiàn)不行，因?yàn)?這個(gè)問題不能類比 斐波拉契數(shù)列, 運(yùn)算結(jié)果的依賴性比斐波拉契數(shù)列更加復(fù)雜。所以作罷。

結(jié)語

以湊零錢問題為例，展示動(dòng)態(tài)規(guī)劃算法的實(shí)戰(zhàn)應(yīng)用價(jià)值。相信本文已經(jīng)解析的很清楚了。就是這么一個(gè)套路。其他最值問題也差不多按照這個(gè)套路，做出最優(yōu)解也只是時(shí)間問題。

但是，現(xiàn)實(shí)中，我們不會(huì)只想知道零錢最少需要多少張，我還想知道零錢怎么組合最優(yōu),怎么解?并且零錢可能無限多么？如果零錢數(shù)目有限，那上面的解法又該如何修改？篇幅太長不利于閱讀，我把解答放到下一章。

盡請期待！

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

算法Balabala湊零錢問題理想版

算法Balabala湊零錢問題理想版

前言

前文回顧

動(dòng)態(tài)規(guī)劃實(shí)戰(zhàn)：理想版湊零錢問題

問題拋出

問題分離

前提

目標(biāo)

問題分解

暴力解法

一重改進(jìn)

二重改進(jìn)

三重改進(jìn)

結(jié)語

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

算法Balabala湊零錢問題理想版

前言

前文回顧

動(dòng)態(tài)規(guī)劃實(shí)戰(zhàn)：理想版湊零錢問題

問題拋出

問題分離

前提

目標(biāo)

問題分解

暴力解法

一重改進(jìn)

二重改進(jìn)

三重改進(jìn)

結(jié)語

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av