动态规划

• 将问题拆分成小问题，先解决最小的问题，然后再一步步的解决大问题
• 寻找大问题和小问题间的关系，通过小问题来求解大问题
• 动态规划的使用条件：
  • 子问题是离散的，不存在相互依赖的关系
  • 存在一定的约束条件，求最值

经典题目

• https://leetcode.com/problems/climbing-stairs/description/ 爬楼梯问题
• https://leetcode.com/problems/house-robber/description/ 偷盗问题
• https://leetcode.com/problems/maximum-subarray/description/ 最大子连续串问题
• https://leetcode.com/problems/coin-change/description/ 零钱问题
• https://leetcode.com/problems/maximum-subarray/description/
• https://leetcode.com/problems/longest-increasing-subsequence/description/
• https://leetcode.com/problems/minimum-path-sum/description/

爬楼梯问题

• 题目：https://leetcode.com/problems/climbing-stairs/description/
• 可以从n-1到第n，也可以从n-2到达n。至于怎么到达n-1和n-2，可以由更小的问题解决

public class ClimbingStairs {
    public int climbStairs(int n) {
        if (n<=2) {
            return n;
        }
        int dp[]=new int[n+1];
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;
        for (int i=3;i<n+1;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}
//子问题：求第1阶和第2阶……第n阶
//确认状态：dp[n]代表n阶台阶有多少种走法
//边界：        dp[1]=1;dp[2]=2;
//状态转移方程：dp[i]=dp[i-1]+dp[i-2];

偷盗问题

• 题目见：https://leetcode.com/problems/house-robber/description/

//子问题：前n个房间的最优解
//确认状态： dp[n]为前n个房间的最优解
//边界：        dp[1];dp[2];
//状态转移方程：Math.max(dp[i-1],dp[i-2]+num[n]);
public class HouseRobber {

    public static void main(String[] args){
        rob(new int[]{1,2,3,1});
    }

    public static int rob(int[] nums) {
        if (nums.length==0) {
            return 0;
        }else if(nums.length==1){
            return nums[0];
        }
        int[] dp=new int[nums.length];
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for (int index=2;index<nums.length;index++){
            dp[index]=Math.max(dp[index-1],dp[index-2]+nums[index]);
        }
        return dp[nums.length-1];
    }
}

最大子连续串问题

• 题目见：https://leetcode.com/problems/maximum-subarray/description/
• 前面两个题都比较直接，dp[n]往往就是题目要求的最优解，这里稍微有点不同，这里的dp[n]是**包含nums[n]**的最大子串，同理dp[n-1]也是包含nums[n-1]的最大子串。所以dp[n-1]+nums[n]表示的就是：……nums[n-1],nums[n]子串

//子问题：求前n个中，包含nums[n]!!!  的最大序列
//确认状态： dp[n]为 包含nums[n]！！的最大连续序列
//边界：        dp[1];dp[2];
//状态转移方程：Math.max(nums[n],dp[n-1]+nums[n]);
public class MaximumSubarray {

    public int maxSubArray(int[] nums) {
        if (nums.length==0) {
            return 0;
        }
        int[] dp=new int[nums.length];
        dp[0]=nums[0];
        int max=dp[0];
        for (int i=1;i<nums.length;i++){
            dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
            max=Math.max(dp[i],max);
        }
        return max;
    }
}

零钱问题

• 题目见：https://leetcode.com/problems/coin-change/description/
• 这个是一个比较典型的动态规划问题，使用给定的零钱（约束条件），求最少使用的零钱数（求最值）
• 整体思路：每个值都尝试使用给定的每种零钱，然后剩余的钱在dp数组中找最优解。

public class CoinChange {

    public static void main(String[] args){
        coinChange(new int[]{1,2,5},11);
    }
    public static int coinChange(int[] coins, int amount) {
        if (amount==0) {
            return 0;
        }
        Arrays.sort(coins);
        int[] dp=new int[amount+1];
        for (int i=0;i<amount+1;i++){
            dp[i]=-1;
        }
        dp[0]=0;
        for (int target=1;target<amount+1;target++){
            for (int coin:coins){
                if (target-coin>=0 && dp[target-coin]!=-1) {
                    if (dp[target]==-1) {
                        dp[target]=dp[target-coin]+1;
                    }else{
                        dp[target]=Math.min(dp[target],dp[target-coin]+1);
                    }
                }
            }
        }
        return dp[amount];
    }
}