Dynamic Programming

First tastes

Before we go into dynamic programming, let see one problem: the classic problem Fibonacci Number:

F $_n$ = F $_{n - 1}$ + F $_{n - 2}$

F $_0$ = F $_1$ = 1

Obvious, O(n) = 2 $^n$ if we use recurtion, so do we have other solution?

1.Memorization

public class Solution2 {
    int fibonacci(int n) {
        int[] res = new int[n]; 
        res[0] = 1;
        res[1] = 1;
        return fibonacci(n - 1, res);
    }

    int fibonacci(int n, int[] res) {
        if (res[n] != 0) { // if we have already calculated it 
            return res[n];
        }
        return fibonacci(n - 1, res) + fibonacci(n - 2, res);
    }
}

2.Tabulation

public class Solution {
    int fibonacci(int n) {
        int[] res = new int[n];
        res[0] = 1;
        res[1] = 1;
        for (int i = 2; i < n; i ++) {
            res[i] = res[i - 1] + res[i - 2];
        }
        return res[n - 1];
    }
}

3.Normal

public class Solution3 {
    int fibonacci(int n) {
        int a = 1;
        int b = 1;
        int c = 0;
        for (int i = 3; i <= n; i ++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

Do you see anything in common?

we memorized some values to avoid solving the overlapping problems. I think this is one of the reasons that we use DP.

what is dynamic programming

In order to solve a large problem(mostly optimal problem), we solve subproblems and store their values in table.

DP is applicable when the subproblems are greatly overlap.
DP is not greedy. DP tries every choice before solving the problem while greedy only travel one branch. So DP is much more expensive than greedy.
In every subproblem, we get the solution by obtains the optimal solution of its subproblem.

0 - 1 Knapstack problem(we cannot choose an item more that once)

Given a set of n unbreakable unique items, each with a weight W $_k$ and a value V $_k$ , determine the subset(the items we choose) of the items such that the total weighe is less than or equal to a given knapsack capacity W and the total value as large as possible.

First step, define the subproblem:

Let OPT[k, x] be the max value of knapsack with number k( $0 <= k <= n$ ) and size w ( $0 <= x < = w$ ) items

if we choose the number k item, OPT[k, x] = OPT[k - 1, x - W $_k$ ] + V $_k$

if we not, OPT[k, x] = OPT[k - 1, x]

There are some other situation we need to consider, we will talk about it later.

Second step, define the base case:

when x = 0, OPT[k, x] = 0

when k = 0, OPT[k, x] = 0

Third step, write the equation:

OPT[k, x] = MAX(OPT[k, x] = OPT[k - 1, x - W $_k$ ] + V $_k$ , OPT[k, x] = OPT[k - 1, x] )

now we see a problem, it is not guaranteed that x - W $_k$ > 0,
so we need to handle it in different condition which we will see in out code.

Final step, coding:

/**
 * 最常規(guī)解法 會得到一個n * weight 大小的表
 */
public class Solution {
    /**
     *
     * @param weight 背包重量上限
     * @param w 商品重量數(shù)組
     * @param v 商品價值數(shù)組
     * @param n 待選擇的商品數(shù)
     * @return
     */
    int knapsack(int weight, int[] w, int[] v, int n) {

        int[][] dp = new int[n + 1][weight + 1];

        /* base case 可以不寫 */
        for (int j = 0; j < weight + 1; j ++) { // 無貨物可選 必然為0
            dp[0][j] = 0;
        }

        for (int i = 0; i < n + 1; i ++) { // 無重量放貨物 必然為0
            dp[i][0] = 0;
        }

        /* dp */
        for (int i = 1; i < n + 1; i++) { // 待選貨物
            for(int j = 1; j < weight + 1; j ++) { // 背包重量
                if (w[i] > j) { // 貨物重量大于背包重量 肯定無法選擇
                    dp[i][j] = dp[i - 1][j];
                    continue;
                }
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); // 做選擇
            }

        }

        return dp[n][weight];
    }
}

Runtime complexity:

$O((weight + 1) \times (n + 1))$ = $O(n ^2)$

Coins choosing problem(we can choose an item more than once)

you are to compute the minus number of coins needed to make change for a given number $m$ , Assume that we have an unlimited supply of coins. Given n denominations , d1 = 1, d2 = 5, d3 = 10 ...

First step: define the subproblem

Let OPT[k, x] be the minimum number of coins to given a change to x ( $0 <= x <= m$ ) using k ( $0 <= k <= n$ ) denominations.

if we choose denominations k, OPT[k, x] = OPT[k, x - d[k]] + 1

attention, here the k is still k not k - 1, because we can choose a coin as many times as we want

if we not, OPT[k, x] = OPT[k - 1, x]

second step：define the base case

when k = 1, OPT[k, x] = x

when x = 0, OPT[k, x] = 0;

third step: define equation:

OPT[k, x] = Min(OPT[k - 1, x], OPT[k, x - d[k]) + 1)

same to above, x-d[k] is not guarantee > 0

final step: coding

public class Solution {
    /**
     *
     * @param m 要組成的金額數(shù)
     * @param d 硬幣數(shù)組 記錄硬幣的面值
     * @return
     */
    public int coins(int m, int[] d) {
        int len = d.length;
        int[][] dp = new int[len][m + 1];

        /* base case */
        for (int j = 0; j < m + 1; j ++) { // dp[0]的面值為1 組成金額j自然需要j個
            dp[0][j] = j;
        }

        for (int i = 0; i < len; i ++) { // 要組成的面值為0
            dp[i][0] = 0;
        }

        /* dp */
        for (int i  = 1; i < len; i ++) { // 待選硬幣
            for (int j = 1; j < m + 1; j ++) { // 要組成的金額
                if (d[i] > m) { // 當(dāng)前硬幣金額大于當(dāng)前金額 無法選擇
                    dp[i][j] = dp[i - 1][j];
                    continue;
                }
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - d[i]] + 1);
            }
        }

        return dp[len - 1][m];
    }

}

Runtime Complexity:

$O(len \times (m + 1))$ = $O(n^2)$

深入理解不可重復(fù)的背包問題

在進(jìn)入這個問題之前，我們在仔細(xì)說一下之前解法：

首先dp中所存的值都是當(dāng)時情況下的最優(yōu)值

兩層for循環(huán)所代表的意思：

第一層for循環(huán)代表待選貨物：當(dāng)i = 1時，我們只有第一個貨物可以選；當(dāng)i = 2時，我們有第一個和第二個貨物可以選，我們在只有第一個貨物可供選擇時作出的決策所導(dǎo)致的結(jié)果的基礎(chǔ)上來決定是否選擇第二個貨物；i = 3時亦然。

第二次for循環(huán)代表背包重量：在當(dāng)前重量下我們是否選擇貨物i，我們只需要考慮是否選擇，無需擔(dān)心選完之后的事情（也是狀態(tài)方程解釋）。

如果選擇：我們將j減去當(dāng)前所選貨物的重量w[i]，并將i - 1 — 意為剩下的背包重量由之前所做過的決策來決定（上一行的數(shù)據(jù)）得到（一定是最優(yōu)）。

如果不選擇：我們保持j不變，并將i - 1，意為剩下的背包重量由之前所做過的來決定得到（一定是最優(yōu)）。再啰嗦一句，這里i - 1是因為，在貨物不可重復(fù)選擇的前提下，一個貨物只能選擇一次，所以一旦我們作出選擇，選擇完該貨物后剩余的重量就只能由之前沒有該貨物選項時的決策導(dǎo)致的結(jié)果來決定了

這個做法其實就體現(xiàn)了dp的核心思想，將大問題轉(zhuǎn)換為子問題，每個子問題拿到的都是該子問題所處情況下的最優(yōu)解，通過解決子問題來到最終答案（但是注意，當(dāng)前層最優(yōu)解并不一定會被下一層的最優(yōu)解采用?。Ｒ欢ㄒ斫?，第二個貨物選擇的決定時在第一個貨物的基礎(chǔ)上進(jìn)行的，不要理解成每個i為單獨的。

可否優(yōu)化？

上面我們所用的解法是最直接的解法，他得到的是一個 $n \times weigh$ _k大小的表，也就是說它嘗試過所有情況（包括一些其實不必嘗試的情況，比如當(dāng)待選貨物為1時，它對所有重量都做了嘗試，然后在問題的解決過程中我們發(fā)現(xiàn)，這些嘗試可能都是徒勞，因為在剩余背包重量很大的情況下，我們有更好的選擇而不是去選擇1）

所以我們考慮，如果將外層for循環(huán)換成重量，會不會好一些呢？我覺得是會的，他會讓我們的表的大小縮小一半?？紤]當(dāng)i = 1時，一旦貨物j的重量超過i，我們就不會再去決策而是直接從上一列取值。但是在之前解法中，當(dāng)i = 1時，他對所有重量都做了決策而非直接取值(這里可以把決策理解為沒有走if分支)。

/**
 * 行列交換 會得到一個weight * n / 2 大小的表
 */
public class Solution2 {
    int knapsack(int weight, int[] w, int[] v, int n) {
        int[][] dp = new int[weight + 1][n + 1];

        /* base case 是0 直接省略*/

        /* dp */
        for (int i = 1; i < weight + 1; i ++) { // 背包重量
            for (int j = 1; j < n + 1; j ++) { // 待選貨物
                if (w[j] > i) {
                    dp[i][j] = dp[i][j - 1];
                    continue;
                }
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - w[j]][j - 1] + v[j]);
            }
        }

        return dp[weight + 1][n + 1];
    }
}

可否繼續(xù)優(yōu)化?

我們繼續(xù)考慮，我們真的有必要將所有情況都記錄進(jìn)數(shù)組嘛？答案是沒必要。如果你觀察的仔細(xì)，你會發(fā)現(xiàn)我們每次計算的時候都只是使用了上一層的值，對于再之前的值，我們不再需要。因此我們只需要保存上一行的數(shù)據(jù)，所以我們只需要維護(hù)一個一維數(shù)組即可。

在此，我們主要解釋決策，if分支不再解釋

如果選擇當(dāng)前貨物：那么需要拿到上一層中重量為j - w[i]時做的決策，也就是d[j - w[i]]（這個決策一定是對這個重量目前最優(yōu)的解）再加上當(dāng)前貨物的價值

如果不選當(dāng)前貨物：那么決策還是當(dāng)前重量對應(yīng)的上一層的決策，也就是d[j]

由此可見，在這個想法下，我們維護(hù)的一維數(shù)數(shù)組的下標(biāo)表示的應(yīng)該是重量

/**
 * 降維解法 只保留上一行數(shù)據(jù)
 * 實際解法維solution1，但是采取降維
 */
public class Solution3 {
    int knapsack(int weight, int[] w, int[] v, int n) {
        int[] dp = new int[n + 1];
        
        /* base case */
        dp[0] = 0;
        
        for(int i = 1; i < n + 1; i ++) { // 待選貨物
            for(int j = 1; j < weight + 1; j ++) { // 背包重量
                if (w[i] > j) {
                    continue;
                }
                dp[j] = Math.max(dp[j - w[i]] + v[i], dp[j]); // 作出選擇
            }
        }

        return dp[weight + 1];
    }
}

深入理解可重復(fù)的背包問題

兩層for循環(huán)所代表的意思：

第一層for循環(huán)代表待選硬幣：當(dāng)i = 1時，我們只有第一個硬幣可以選；當(dāng)i = 2時，我們有第一個和第二個硬幣可以選，我們在第一個硬幣選擇與否所造成結(jié)果的基礎(chǔ)上來決定是否選擇第二個硬幣；i = 3時亦然。

第二次for循環(huán)代表要組成的面值，在當(dāng)前面值下我們是否選擇硬幣i，我們只需要考慮是否選擇，無需擔(dān)心選完之后的事情（也是狀態(tài)方程解釋）。

如果選擇：我們將j減去當(dāng)前所選硬幣的面值d[i]，注意這里，i不變，這是因為，在硬幣可以重復(fù)選擇的前提下，我們作出使用這個硬幣的決定后，剩余的重量還是可以繼續(xù)使用該硬幣。試想，當(dāng)前選擇完硬幣后，待組成面額一定會減小，這個待組成面額還是要使用包括當(dāng)前硬幣在內(nèi)的所有可選擇的硬幣，所以我們要依賴之前所作出的所有決策而不僅僅是沒有該面額硬幣時所作出的決策（到當(dāng)前行的前幾列以及前一行的前幾列）。

如果不選擇：我們保持j不變，并將i - 1，這里i-1是因為，如果當(dāng)前選擇不用，那么代表我們對當(dāng)前面額的硬幣的使用已經(jīng)結(jié)束（可以理解為我們在更大重量時或許多次使用這個硬幣，但是在這次選擇之后，剩余的重量我們將會不會再使用該面額），剩下待組成面值依靠之前沒有該面額的硬幣時所作出的決策導(dǎo)致的結(jié)果（上一行）來得到（一定是最優(yōu)）。

可否優(yōu)化？

同不可重復(fù)的背包問題一樣，如果外層循環(huán)為硬幣面值，會有很多無用數(shù)據(jù)，比如當(dāng)i = 0，也就是硬幣面值為1時，如果代組成金額為100，我們就會把0 - 100都便利一遍，這顯然是沒有必要的，因為100個1組成100顯然不是最好的組成方法。

所以我們考慮把外層換成待組成的金額值，原因與可重復(fù)背包問題一直，可以減少決策(去到if分支的情況更多)

public class Solution2 {
    public int coins(int m, int[] d) {
        int len = d.length;
        int[][] dp = new int[m + 1][len];

        /* base case */
        for(int j = 0; j < len; j ++) { // 待組成金額為0
            dp[0][j] = 0;
        }

        for (int i = 0; i < m + 1; i ++) { //硬幣面值為1
            dp[i][0] = i;
        }

        /* dp */
        for (int i = 1; i < m + 1; i ++) {
            for (int j = 1; j < len; j ++) {
                if (d[j] > i) {
                    dp[i][j] = dp[i][j - 1];
                    continue;
                }
                dp[i][j] = Math.min(dp[i][j - 1], dp[i - d[j]][j - 1] + 1);
            }
        }
        
        return dp[m][len - 1];
    }
}

可否繼續(xù)優(yōu)化

既然不可重復(fù)背包問題的空間復(fù)雜度是能夠繼續(xù)優(yōu)化的，那么是否可以采取相同的思路對可重復(fù)背包問題來進(jìn)行優(yōu)化呢？我們來思考一下。

首先，我們之所以可以優(yōu)化不可重復(fù)背包問題，是因為我們計算當(dāng)前情況時，只需使用到上一行的數(shù)據(jù)，所以我們只需要維護(hù)一個維護(hù)一維數(shù)組。但是，可重復(fù)背包問題并不是這樣。

如果選擇：我們將j減去當(dāng)前所選硬幣的面值d[i]，注意這里，i不變，因為這個硬幣可以重復(fù)使用，意為剩下面值依賴與有該面額硬幣以及僅沒有當(dāng)前面額硬幣時所做的決策（上一行 或者當(dāng)前行的之前列）得到（一定是最優(yōu)）。

如果不選擇：我們保持j不變，并將i - 1，如果我們選擇不用，那么表示我們對當(dāng)前面額的硬幣的使用結(jié)束，意為剩下的面值由之前沒有當(dāng)前面額硬幣時所做過的來決策來完成（上一行，因為現(xiàn)在決定當(dāng)前行所對應(yīng)的硬幣不再使用，所以剩下的面值只能由之前的硬幣得到而不能再使用當(dāng)前硬幣）得到（一定是最優(yōu)）。

很明顯，我們在當(dāng)前做決定時，不僅僅用到之前的行，還可能會用到之前的列，所以，不可重復(fù)背包問題的優(yōu)化方式不再可取。

難道這就說明我們可重復(fù)背包問題的空間復(fù)雜度無法優(yōu)化嘛？并不是，我們可以采取別的思路。

我們再次思考，我們?nèi)绾文軌蚧谥白鞒龅臎Q策來完成當(dāng)前決策呢？其實有一種方法：當(dāng)我們金額增加時，我們必然是要調(diào)整我們硬幣的組成，可能是只增加一枚新的硬幣，也可能是增加一個較大的新硬幣拿走一個較小的之前選擇的硬幣。不管是哪種情況，我們都是基于之前的決策完成的。直接增加硬幣不需要解釋了，我們直接挑最合適的就可以（雖然我覺得這種情況不會出現(xiàn)）。將較小的硬幣替換成一個較大的硬幣這種情況我們可以思考一下。

我們可以換一種方式來實現(xiàn)這個替換：因為我們總歸要選一枚硬幣，只是我們不知道應(yīng)該選哪個。解決這個問題很簡單，我們將每個硬幣都選一下試試看，然后再看減掉這個新選擇的硬幣面額后剩下的待組成金額的dp（這個剩下的待組成金額一定是我們已經(jīng)在之前的dp決策中得到過的，所以我們有組成這個剩下待組成金額的最優(yōu)解），選完哪個硬幣后得到的dp + 1最小，我們就應(yīng)該選擇哪個硬幣。

/**
 * 降維 但是思路與不可重復(fù)背包問題的降維思路不同
 * 可重復(fù)背包問題無法采用不可重復(fù)背包問題的降維思路，因為所需要的數(shù)據(jù)不一定只來源與上一行，也可能來源于當(dāng)前行的之前列
 */
public class Solution3 {
    public int coins(int m, int[] d) {
        int len = d.length;
        int[] dp = new int[m + 1];

        /* base case 待組成金額為0 其他待組成金額待求 所以要設(shè)置成無窮 */
        dp[0] = 0;
        for(int i = 1; i < m + 1; i ++) {
            dp[i] = Integer.MAX_VALUE;
        }

        /* dp */
        for (int i = 1; i < m + 1; i ++) { // 待組成金額
            for (int j = 0; j < len; j ++) { // 硬幣面額
                if (d[j] > i) { // 硬幣面額大于代組成的面額
                    continue;
                }
                dp[i] = Math.min(dp[i - d[j]] + 1, dp[i]); //決策 選取當(dāng)前硬幣，剪掉當(dāng)前硬幣面額得到已經(jīng)決策過的dp，拿到最優(yōu)
            }
        }

        return dp[m + 1];
    }
}

背包問題的內(nèi)在規(guī)則

背包問題總會有一個可供選擇的“集合” 和一個上限

集合可能對應(yīng)一個值，這個值對應(yīng)上限，從集合中選取的個數(shù)對應(yīng)解

集合也可能對應(yīng)一系列數(shù)值，有的值對應(yīng)上限，有的值對應(yīng)解

0-1背包問題，n種商品為選擇集合， W為上限。這個題目比較特殊，那就是它的選擇集合并不單單是一個值n，對于每一個n，都有一個[w, v]與其關(guān)聯(lián)，w用來對應(yīng)上限， v用來對應(yīng)問題所求。
硬幣問題，各種硬幣為選擇集合，要組成的錢數(shù)為上限，這個題目就是比較常規(guī)的題目對于每個硬幣, 都有一個面額與其關(guān)聯(lián)，硬幣的面額用來決定上限，硬幣的個數(shù)用來對應(yīng)所求

在github上有更多DP問題的一些解法

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

動態(tài)規(guī)劃基礎(chǔ)問題的固定解法思路

動態(tài)規(guī)劃基礎(chǔ)問題的固定解法思路

Dynamic Programming

First tastes

what is dynamic programming

0 - 1 Knapstack problem(we cannot choose an item more that once)

Coins choosing problem(we can choose an item more than once)

深入理解不可重復(fù)的背包問題

可否優(yōu)化？

可否繼續(xù)優(yōu)化?

深入理解可重復(fù)的背包問題

可否優(yōu)化？

可否繼續(xù)優(yōu)化

背包問題的內(nèi)在規(guī)則

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

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

動態(tài)規(guī)劃基礎(chǔ)問題的固定解法思路

Dynamic Programming

First tastes

what is dynamic programming

0 - 1 Knapstack problem(we cannot choose an item more that once)

Coins choosing problem(we can choose an item more than once)

深入理解不可重復(fù)的背包問題

可否優(yōu)化？

可否繼續(xù)優(yōu)化?

深入理解可重復(fù)的背包問題

可否優(yōu)化？

可否繼續(xù)優(yōu)化

背包問題的內(nèi)在規(guī)則

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

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

可否優(yōu)化？