动态规划

2017-07-18

× 文章目录

1. 什么是动态规划？
定义：满足对阶段决策过程的最优化问题，一般都可以用动态规划来解决。

1.1 特性：

动态规划的本质是对问题状态的定义和状态转移方程的定义
动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解可以由上一次子问题的解推出。使用动态规划时间复杂度仅为多项式时间，因此比回溯法、暴力枚举等方法快许多
“缓存”、“重叠子问题”、“记忆化”
递归
无后效性，即满足最优性原理

1.2 思想： 通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。如何拆分问题才是动态规划的核心，而拆分问题，靠的就是状态的定义和状态转移方程的定义

1.2.1 什么是状态的定义？
- 请看这
- 状态这个东西我现在无法明确描述并给予定义，希望在真正理解应用动态规划后再回来解释。
1.2.2 什么是状态转移方程？
- 上述状态定义好之后，状态和状态之间的关系式，就叫做状态转移方程。
- 状态转移方程就是带有条件的递推式

注：一个问题可能会有多个定义，存在一个不满足最优性原理的定义，不代表该问题不适用动态规划。

2. 实例
数学类的、计算机类的东西，你明白了定义，但是不上手体会，记忆不会牢固，也不能真正理解应用。

动态规划基本步骤：
- （1）找出最优解的性质，并刻画其结构特征
- （2）递归的定义最优解
- （3）以自底向上的方式计算出最优值
- （4）根据计算最优值时得到的信息，构造最优解

2.1 入门
【问题】如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？
【解答】

定义问题（状态）：要凑够i元最少需要几个硬币。

状态转移方程：当前要凑够i元，比这更小一点的问题有，我选择了其中一个硬币V_j（V_j表示一种硬币的值）$$d(i) = min{d(i - V_j)}+1$$其中$i - V_j >= 0$,V_j表示第j个硬币的面值；
有了状态和状态转移方程，这个问题就基本解决了。

Talk is cheap, show me the Code!

/**
 * @Author:liujifang
 * @Description: 如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？
 * @Date: Created in 22:28 2017/8/21
 */
public class MinCoins {
	/**
     * @param money 需要凑够的钱
     * @param coins 硬币种类
     * @return 最少的硬币数量
     */
    public static int solution(int money, int[] coins){
        int n = coins.length;
        int[] dp = new int[money+1];
        dp[0] = 0;
        for (int i = 1; i <= money; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        for (int i = 1; i <= money; i++) {
            for (int j = 0; j < n; j++) {
                if(coins[j] <= i && dp[i-coins[j]]+1 < dp[i])
                    dp[i] = dp[i-1]+1;
            }
        }
        return dp[money];
    }

    public static void main(String[] args) {
        int[] coins = {1,3,5};
        int money = 11;
        System.out.println(solution(money, coins));
    }
}

2.2 初级
上面讨论了一个非常简单的例子。现在让我们来看看对于更复杂的问题，如何找到状态之间的转移方式（即状态转移方程）。

【问题】LIS：一个序列有N个数：A[1],A[2],…,A[N]，求出最长非降子序列的长度。
【解答】

状态：考虑从A[1],..A[i]的最长非降子序列的长度，其中i<N，定义d(i)为前 i 个数中以 A[i] 结尾的最长非降子序列的长度。
状态转移方程：如果我们已经求出了d(1)到d(i)，那么$$d(i) = max{1, d(j)+1},其中j<i,A[j]<A[i]$$

【代码】

/**
 * @Author:liujifang
 * @Description: 一个序列有N个数：A[1],A[2],...,A[N]，求出最长非降子序列的长度。
 * @Date: Created in 23:17 2017/8/21
 */
public class LIS {
    /**
     * @param arr 待求最长上升子序列的数组
     * @return 最长上升子序列
     * @desc 时间复杂度为n^2
     */
    public static int solution(int[] arr) {
        int m = 0;
        int n = arr.length;
        int[] dp = new int[n];
        int ans = 0;
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            m = 0;
            for (int j = 0; j < i; j++) {
                if (arr[j] <= arr[i] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            }
            if (dp[i] > ans) ans = dp[i];
        }
        return ans;
    }

    /**
     * @desc 时间复杂度为nlog(n)
     */
    public static int solution2(int[] arr) {
        int n = arr.length;
        int[] dup = new int[n];
        dup[0] = 1;
        int size = 0;
        int j;
        for (int i = 1; i < n; i++) {
            if (arr[i] < dup[0]) {
                j = 1;
            } else if (arr[i] > dup[size]) {
                j = ++size;
            } else {
                j = bs(dup, size, arr[i]);
            }
            dup[j] = arr[i];
        }
        return size;
    }

    private static int bs(int[] dup, int size, int key) {
        int low = 0;
        int high = size;
        int mid;
        while (low < high) {
            mid = (low + high) / 2;
            if (key > dup[mid] && key <= dup[mid + 1])
                return mid + 1;
            else if (key < dup[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
        return 0;
    }

    public static void main(String[] args) {
        int[] arr = {10, 2, 4, 12, 8};
        System.out.println(solution2(arr));
    }
}

2.3 中级
【问题】平面上有N＊M个格子，每个格子中放着一定数量的苹果。你从左上角的格子开始，每一步只能向下走或是向右走，每次走到一个格子上就把格子里的苹果收集起来，这样下去，你最多能收集到多少个苹果。
【解答】

定义问题（状态）：走到 i * j 个格子的时候最多能收集到多少个苹果。
状态转移方程：假设格子（或者称为棋盘）是一个二维数组cell[N][M]，二维数组的值就是格子上的苹果数。从cell[0][0]到cell[i][j]能得到的最大苹果数为dp[i][j]。则：$$dp[i][j] = max { dp[i-1][j],dp[i][j-1]} + cell[i][j]$$

【代码】

package javastudy.algorithm.dp;
/**
 * @Author:liujifang
 * @Description: 平面上有N＊M个格子，每个格子中放着一定数量的苹果。你从左上角的格子开始，每一步只能向下走或是向右走，每次走到一个格子上就把格子里的苹果收集起来，这样下去，你最多能收集到多少个苹果。
 * @Date: Created in 22:25 2017/8/22
 */
public class ChessMetric {
    public static void main(String[] args) {
        int[][] arr = {{1,2,3},{2,3,1},{6,3,5}};
        int max = maxApples(arr);
        System.out.println(max);
    }

    public static int maxApples(int[][] arr){
        int result = 0;
        int n = arr.length;
        int m = arr[0].length;
        int[][] dp = new int[n][m];
        //初始化dp[][]
        dp[0][0] = arr[0][0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i-1][0] + arr[i][0];
        }
        for (int i = 1; i < m; i++) {
            dp[0][i] = dp[0][i-1] + arr[0][i];
        }
        //dp过程
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + arr[i][j];
            }
        }
        result = dp[n-1][m-1];
        return result;
    }

    private static int max(int i, int j) {
        return i>j?i:j;
    }
}

2.4 中高级
【问题】无向图G有N个结点，它的边上带有正的权重值。你从结点1开始走，并且一开始的时候你身上带有M元钱。如果你经过结点i，那么你就要花掉S[i]元(可以把这想象为收过路费)。如果你没有足够的钱，就不能从那个结点经过。在这样的限制条件下，找到从结点1到结点N的最短路径。或者输出该路径不存在。如果存在多条最短路径，那么输出花钱数量最少的那条。
【解答】…未完待续