動(dòng)態(tài)規(guī)劃應(yīng)用場(chǎng)景

求一個(gè)問(wèn)題的最優(yōu)解（通常是求最大值或者最小值），而且該問(wèn)題能夠分解成若干個(gè)子問(wèn)題祠锣，并且子問(wèn)題之間還有重疊的更小的子問(wèn)題绒障，就可以考慮用動(dòng)態(tài)規(guī)劃來(lái)解決。

相對(duì)遞歸的優(yōu)勢(shì)

相同的問(wèn)題使用動(dòng)態(tài)規(guī)劃喘帚，可避免子問(wèn)題重復(fù)計(jì)算，極大減小空間復(fù)雜度咒钟。

動(dòng)態(tài)規(guī)劃解題思路

1. 確定狀態(tài)
   ? 研究最優(yōu)策略的最后一步
   ? 優(yōu)化為子問(wèn)題
2. 轉(zhuǎn)移方程
   ? 根據(jù)子問(wèn)題定義直接得到
3. 初始條件和邊界情況
   ? 仔細(xì)吹由，考慮周全
4. 計(jì)算順序
   ? 利用之前的計(jì)算結(jié)果

硬幣問(wèn)題

遞歸

static int coinChangeRecall(int amount, int[] coins) {
    if (amount == 0) return 0;
    int res = 14;
    for (int coin : coins) {
        if (amount >= coin) {
            res = Integer.min(res, coinChangeRecall(amount - coin, coins) + 1);
        }
    }
    return res;
}

動(dòng)態(tài)規(guī)劃

static int coinChange(int[] coins, int amount) {
    int[] init = new int[amount + 1];
    init[0] = 0;
    for (int i = 1; i <= amount; i++) {
        init[i] = Integer.MAX_VALUE;
        for (int coin : coins) {
            if (i >= coin && init[i - coin] != Integer.MAX_VALUE) {
                init[i] = Math.min(init[i - coin] + 1, init[i]);
            }
        }
    }
    if (init[amount] == Integer.MAX_VALUE) {
        init[amount] = -1;
    }
    return init[amount];

}

背包問(wèn)題

遞歸

static int maxPackageValueRecall(int packageSpace, int[][] goods) {
    if (packageSpace == 0) return 0;
    int res = 0;
    for (int[] good : goods) {
        if (packageSpace > good[0]) {
            res = Integer.max(res, maxPackageValueRecall(packageSpace - good[0], goods) + good[1]);
        }
    }
    return res;
}

動(dòng)態(tài)規(guī)劃

static int maxPackageValue(int packageSpace, int[][] goods) {
    int[] init = new int[packageSpace + 1];
    init[0] = 0;
    for (int s = 1; s <= packageSpace; s++) {
        init[s] = 0;
        for (int[] good : goods) {
            if (good[0] < s) {
                init[s] = Math.max(init[s - good[0]] + good[1], init[s]);
            }
        }
    }
    return init[packageSpace];
}

斐波那契數(shù)列

遞歸

static int fibRecall(int n) {
    if (n == 1 || n == 2) return 1;
    else {
        return fibRecall(n - 1) + fibRecall(n - 2);
    }
}

動(dòng)態(tài)規(guī)劃

static int fib(int n) {
    int[] init = new int[n + 1];
    init[1] = 1;
    init[2] = 1;
    for (int i = 3; i <= n; i++) {
        init[i] = init[i - 1] + init[i - 2];
    }
    return init[n];
}

唯一路徑 動(dòng)態(tài)規(guī)劃

static int GetUniqueRoadCount(int m, int n) {
    int[][] init = new int[m][n];
    int i, j;
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            if (i == 0 || j == 0) {
                init[i][j] = 1;
            } else {
                init[i][j] = init[i - 1][j] + init[i][j - 1];
            }
        }
    }
    return init[m - 1][n - 1];
}

最短步數(shù) 動(dòng)態(tài)規(guī)劃

static int minStep(int[] stepLengths, int sumLength) {
    int[] init = new int[sumLength + 1];
    init[0] = 0;
    for (int i = 1; i <= sumLength; i++) {
        init[i] = Integer.MAX_VALUE;
        for (int j : stepLengths) {
            if (i >= j && init[i - j] != Integer.MAX_VALUE) {
                init[i] = Math.min(init[i], init[i - j] + 1);
            }
        }
    }
    if (init[sumLength] == Integer.MAX_VALUE) {
        return -1;
    }
    return init[sumLength];
}