算法-动态规划

动态规划简介

动态规划（英语：Dynamic programming，DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划问题，需要将给定问题分成若干个子问题，再合并子问题的解而得到原问题的解。通常许多子问题很相似，不同于递归方法，动态规划仅仅解决子问题一次，从而减少计算量：一旦某个子问题的解已经算出，则将其记忆化存储，以方便下一次需要同一个子问题解时直接返回。

动态规划需要满足的三个性质：

1. 最优子结构性质：问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构性质。

2. 子问题重叠问题：递归算法自顶向下对问题进行求解过程中，每次产生的子问题并不总是新问题，有些子问题会重复计算多次。

3. 无后效性：各个阶段按照一定顺序排列好之后，对于某个给定的状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的状态。

斐波那契问题

递归算法的复杂度为2^n，而DP算法的时间复杂度为O(N)，原因在于递归算法过程中存在着大量的重叠子问题，随着N增大，问题规模呈指数增长。也可以采用记忆化搜索，每次求子问题的解之前先取数组中查看该子问题是否已经解决，如果解决了直接返回，没有解决将结果添加到数组中。记忆化搜索是自顶向下的思考问题，而DP则是自底向上的思考问题。

public class Fib {
    //O(2^N)
    public int fib(int n) {
        if (n == 0)
            return 0;
        if (n == 1)
            return 1;
        return fib(n-1) + fib(n-2);
    }

    //O(N)
    public int fib2(int n) {
        int[] res = new int[n + 1];
         res[0] = 0;
        res[1] = 1;
        for (int i = 2; i < n+1; i++){
            res[i] = res[i-1] + res[i-2];
        }
        return res[n];
    }

    public static void main(String[] args) {
        Fib fib = new Fib();
        long startTime = System.currentTimeMillis();
        int n = 42;
        System.out.println("fib(" + n + ") = " + fib.fib(n));
        System.out.println("time : " + (System.currentTimeMillis() - startTime));

        long startTime1 = System.currentTimeMillis();
        System.out.println("fib(" + n + ") = " + fib.fib2(n));
        System.out.println("time : " + (System.currentTimeMillis() - startTime1));

    }
}

LeetCode相关题目

将自己做的LeetCode相关题目整理了一下，以方便以后复习查看。

ClimbingStairs_70

爬楼梯问题：

package leetcode.dp;

/**
 * Created by cdx0312
 * 2018/4/11
 */
public class ClimbingStairs_70 {
    //dp
    public int climbStairs(int n) {
        int[] res = new int[n + 1];
        res[1] = 1;
        res[2] = 2;
        for (int i = 3; i <= n; i++) {
            res[i] = res[i-1] + res[i - 2];
        }
        return res[n];
    }

    //递归
    public int climbStairs1(int n) {
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        return climbStairs1(n-1) + climbStairs1(n-2);
    }
}

CoinChange_322

无限数量的硬币，凑成给定的值，选取所需硬币个数最少的。

递归方法为组合问题，将所有可能的找出来，选出其中最少的。复杂度O(2^n * n)

DP方法，维护一个数组，长度为amount+1, 初始值设置为amount+1,状态转移方程为dp[i] = min(dp[i], dp[i- coins[j] + 1])

package leetcode.dp;

/**
 * Created by cdx0312
 * 2018/4/12
 */
public class CoinChange_322 {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0)
            return 0;
        int n = amount + 1;
        for (int coin : coins) {
            int curr = 0;
            if (amount >= coin) {
                int next = coinChange(coins, amount - coin);
                if (next >= 0)
                    curr = 1 + next;
            }
            if (curr > 0)
                n = Math.min(n, curr);
        }
        return n == amount + 1 ? -1 : n;
    }

    public int coinChange1(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for (int i = 0; i < dp.length; i++)
            dp[i] = amount + 1;
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i)
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        System.out.println(new CoinChange_322().coinChange1(new int[]{2}, 3));
    }

}

BestTimeToBuyAndSellStockWithCoolDown_309

题目是股票问题的变种，数组prices表示股票第i天的价格，可以多次买卖，限制只有手里没有股票时可以买，同时当你卖了股票，第二天不可以购买。股票问题其实比较简单，如果不限制第二天不可以买的话，就是一个简单的数组最大连续子数组和问题，添加之后需要，有三种状态，买，卖，休息。

public int maxProfit(int[] prices) {
    if (prices.length <= 1)
        return 0;
    int[] s0 = new int[prices.length];
    int[] s1 = new int[prices.length];
    int[] s2 = new int[prices.length];
    s1[0] = -prices[0];
    s2[0] = Integer.MIN_VALUE;
    for (int i = 1; i < prices.length; i++) {
        s0[i] = Math.max(s0[i-1], s2[i-1]);
        s1[i] = Math.max(s1[i-1], s0[i-1] - prices[i]);
        s2[i] = s1[i-1] + prices[i];
    }
    return Math.max(s0[prices.length - 1], s2[prices.length - 1]);
}

CombinationSumIV_377

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

package leetcode.dp;

import java.util.Arrays;

/**
 * Created by cdx0312
 * 2018/4/12
 */
public class CombinationSumIV_377 {
    public int combinationSum4(int[] nums, int target) {
        if (target == 0)
            return 1;
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (target >= nums[i])
                res += combinationSum4(nums, target - nums[i]);
        }
        return res;
    }

    public int combinationSum41(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j <nums.length; j++) {
                if (i - nums[j] >= 0)
                    dp[i] += dp[i - nums[j]];
            }
        }
        return dp[target];
    }
}

最长公共子序列问题

package leetcode.dp;

/**
 * Created by cdx0312
 * 2018/4/12
 * 最长公共子序列
 */
public class LongestCommonSequence {

    //递归
    public int longest(String s1, String s2) {
        if (s1.length() == 0 || s2.length() == 0)
            return 0;
        return longest(s1, s2, s1.length()-1, s2.length()-1);
    }

    private int longest(String s1, String s2, int m, int n) {

        if (m < 0 || n < 0)
            return 0;
        if (s1.charAt(m) == s2.charAt(n))
            return 1 + longest(s1,s2,m-1,n-1);
        else
            return Math.max(longest(s1,s2,m-1, n), longest(s1,s2,m,n-1));
    }

    public static void main(String[] args) {
        LongestCommonSequence LCS = new LongestCommonSequence();
        String s1 = "abcd";
        String s2 = "abcdefg";
        System.out.println(LCS.longest(s1,s2));
        System.out.println(LCS.longest2(s1,s2));
    }

    //DP
    public int longest2(String s1, String s2) {
        if (s1.length() == 0 || s2.length() == 0)
            return 0;
        int len1 = s1.length();
        int len2 = s2.length();
        int[][] dp = new int[len1+1][len2+1];
        for (int i = 0; i <= len1; i++)
            dp[i][0] = 0;
        for (int i = 0; i <= len2; i++)
            dp[0][i] = 0;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s1.charAt(i-1) == s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[len1][len2];
    }
}

最长上升子序列问题

package leetcode.dp;

import java.util.Arrays;

/**
 * Created by cdx0312
 * 2018/4/12
 * 最长上升子序列问题
 */
public class LongestIncreasingSubsequence_300 {
    //O(N^2)
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0)
            return 0;
        int[] dp = new int[nums.length];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = 1;
        }
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        System.out.println(Arrays.toString(dp));
        int max = dp[0];
        for (int i = 1; i < dp.length; i++) {
            max = Math.max(dp[i], max);
        }
        return max;
    }

    public static void main(String[] args) {
        int[] arr = {1,3,6,7,9,4,10,5,6};
        System.out.println(new LongestIncreasingSubsequence_300().lengthOfLIS(arr));

    }
}

0-1背包问题

package leetcode.dp;

/**
 * Created by cdx0312
 * 2018/4/12
 * 0-1背包问题
 */
public class Knapsack01 {
    int[][] dp;
    //递归
    public int knapscak01(int[] w, int[] v, int C) {
        dp = new int[w.length][C + 1];
        return bestValue(w,v, w.length-1,C);
    }

    private int bestValue(int[] weight, int[] value, int index, int capacity) {
        if (index < 0 || capacity <= 0)
            return 0;
        int res = bestValue(weight, value, index - 1, capacity);
        if (capacity > weight[index])
            res = Math.max(value[index] + bestValue(weight, value, index - 1, capacity - weight[index]), res);
        return res;
    }

    //dp O(N*C) O(N*C)
    public int knapscak01_2(int[] w, int[] v, int C) {
        int n = w.length;
        if (n == 0)
            return 0;
        int[][] dp = new int[n][C + 1];
        for (int j = 0; j <= C; j++)
            dp[0][j] = (j >= w[0] ? v[0] : 0);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= C; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= w[i])
                    dp[i][j] = Math.max(dp[i][j], v[i] + dp[i-1][j-w[i]]);
            }
        }
        return dp[n-1][C];
    }

    //dp O(C) O(N*C)
    public int knapscak01_3(int[] w, int[] v, int C) {
        int n = w.length;
        if (n == 0)
            return 0;
        int[][] dp = new int[2][C + 1];
        for (int j = 0; j <= C; j++)
            dp[0][j] = (j >= w[0] ? v[0] : 0);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= C; j++) {
                dp[i%2][j] = dp[(i-1)%2][j];
                if (j >= w[i])
                    dp[i%2][j] = Math.max(dp[i%2][j], v[i] + dp[(i-1)%2][j-w[i]]);
            }
        }
        return dp[(n-1)%2][C];
    }

    //dp O(C) O(N*C)
    public int knapscak01_4(int[] w, int[] v, int C) {
        int n = w.length;
        if (n == 0)
            return 0;
        int[] dp = new int[C + 1];
        for (int j = 0; j <= C; j++)
            dp[j] = (j >= w[j] ? v[0] : 0);
        for (int i = 1; i < n; i++) {
            for (int j = C; j >= w[i]; j--) {
                dp[j] = Math.max(dp[j], v[i] + dp[j-w[i]]);
            }
        }
        return dp[C];
    }
}

完美平方数

package leetcode.dp;

import java.util.Arrays;

/**
 * Created by cdx0312
 * 2018/4/11
 */
public class PerfectSquares_279 {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        for (int i = 0; i <= n; i++)
            dp[i] = Integer.MAX_VALUE;
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= (int)Math.sqrt(i); j++) {
                dp[i] = Math.min(dp[i], dp[i-j*j] + 1);
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(new PerfectSquares_279().numSquares(13));
    }
}

机器人走路问题

package leetcode.dp;

import java.util.Arrays;

/**
 * Created by cdx0312
 * 2018/4/11
 */
public class UniquePaths_62 {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i < m; i++)
            dp[i][0] = 0;
        for (int j = 0; j < n; j++)
            dp[0][j] = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == 1 && j == 1)
                    dp[i][j] = 1;
                else
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        for (int i = 0; i <= m; i++)
            System.out.println(Arrays.toString(dp[i]));
        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(new UniquePaths_62().uniquePaths(3,7));
    }
}

间隔打劫问题

package leetcode.dp;

/**
 * Created by cdx0312
 * 2018/4/11
 */
public class HouseRobber_198 {
    //dp[i]表示考虑抢劫nums[i...n]所获得的最大收益
    int[] dp;
    public int rob(int[] nums) {
        dp = new int[nums.length];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = -1;
        }
        return tryRob(nums, 0);
    }

    //考虑抢劫nums[index..nums.length]这个范围内的所有房子
    private int tryRob(int[] nums, int index) {
        if (index >= nums.length)
            return 0;
        if (dp[index] != -1)
            return dp[index];
        int res = 0;
        for (int i = index; i < nums.length; i++) {
            res = Math.max(res,nums[i] + tryRob(nums, i + 2));
        }
        dp[index] = res;
        return res;
    }

    //dp方法
    public int rob1(int[] nums) {
        int n = nums.length;
        if (n == 0)
            return 0;
        int[] dps = new int[n];
        for (int i = 0; i < n; i++)
            dps[i] = -1;
        dps[n-1] = nums[n-1];
        for (int i = n -2; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                dps[i] = Math.max(dps[i], nums[j] + (j+2 < n ? dps [j+2] : 0));
            }
        }
        return dps[0];
    }
}

间隔打劫问题2–收尾相连

package leetcode.dp;

/**
 * Created by cdx0312
 * 2018/4/11
 */
public class HouseRobberII_213 {
    public int rob(int[] nums) {
        if (nums.length == 1)
            return nums[0];
        return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));
    }

    private int rob(int[] nums, int lo, int hi) {
        int include = 0, exclude = 0;
        for (int j = lo; j <= hi; j++) {
            int i = include, e = exclude;
            include = e + nums[i];
            exclude = Math.max(e, i);
        }
        return Math.max(include, exclude);
    }
}