动态规划

动态规划应用场景

求一个问题的最优解（通常是求最大值或者最小值），而且该问题能够分解成若干个子问题，并且子问题之间还有重叠的更小的子问题，就可以考虑用动态规划来解决。

相对递归的优势

相同的问题使用动态规划，可避免子问题重复计算，极大减小空间复杂度。

动态规划解题思路

1. 确定状态
   • 研究最优策略的最后一步
   • 优化为子问题
2. 转移方程
   • 根据子问题定义直接得到
3. 初始条件和边界情况
   • 仔细，考虑周全
4. 计算顺序
   • 利用之前的计算结果

硬币问题

递归

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;
}

动态规划

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];

}

背包问题

递归

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;
}

动态规划

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];
}

斐波那契数列

递归

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

动态规划

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];
}

唯一路径 动态规划

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];
}

最短步数 动态规划

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];
}