一、动态规划简介

动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

1.1 动态规划组成部分

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

1.2 与其他算法的关系

分治 动态规划 贪心
适用类型 通用 优化 优化
子问题 每个都不同 有很多重复 只有一个
最优子结构 没有要求 必须满足 必须满足
子问题数 全部都要解 全部都要解 只解一个

二、线性动态规划

线性动态规划的主要特点是状态的推导是按照问题规模 i 从小到大依次推过去的，较大规模的问题的解依赖较小规模的问题的解。这里问题规模为 i 的含义是考虑前 i 个元素 [0..i] 时问题的解。

2.1 单串问题

连续子数组的最大和

⚡ 动态规划

class Solution {
    public int maxSubArray(int[] nums) {
        //定义最大和dp[i]中必须包含元素nums[i]
        int n = nums.length;
        int ans = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i - 1] > 0) {
                    nums[i] += nums[i - 1];
            }
            ans = Math.max(nums[i], ans);
        }
        return ans;
    }
}

换硬币

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] f = new int[amount + 1];
        int n = coins.length;
        f[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            f[i] = Integer.MAX_VALUE;

            for (int j = 0; j < n; ++j) {
                if (i >= coins[j] && f[i - coins[j]] != Integer.MAX_VALUE) {//边界情况
                    f[i] = Math.min(f[i - coins[j]] + 1, f[i]); //转移方程
                }
            }
        }
        if (f[amount] == Integer.MAX_VALUE) {
            f[amount] = -1;
        }
        return f[amount];
    }
}

青蛙跳台阶问题

⚡ 动态规划

class Solution {
    public int numWays(int n) {
        if(n <= 1) return 1;
        int[] dp = new int[n+1];
        dp[0] = 1; dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
        }
        return dp[n];
    }
}

⚡ 上面方法优化空间复杂度

class Solution {
    public int numWays(int n) {
        int a = 1, b = 1;
        int sum = 1;
        for (int i = 2; i <= n; ++i) {
            sum = (a + b) % 1000000007;
            b = a;
            a = sum;
        }
        return sum;
    }
}

跳跃游戏

⚡ 动态规划 Time: O(n2) Space: O(n)

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        boolean[] dp = new boolean[n];
        dp[0] = true;
        for (int i = 1; i < n; ++i) {
            dp[i] = false;
            for (int j = 0; j < i; ++j) {
                if(dp[j] && j + nums[j] >= i) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n - 1];
    }
}

⚡ 贪心 Time: O(n) Space: O(1)

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int maxlen = 0;
        for (int i = 0; i < n; ++i) {
            if (maxlen >= i) {
                maxlen = Math.max(maxlen, nums[i] + i);
                if (maxlen >= n - 1) return true;
            }
        }
        return false;
    }
}

最长递增子序列⭐

⚡ 动态规划

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int max = 1;

        for (int i = 0; i < n; ++i) {
            dp[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

最长递增子序列的个数

⚡ 动态规划

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] lengths = new int[n];//存以i号位置元素结尾的最长子序列
        int[] counts = new int[n];//以i位置元素结尾的最长子序列的数量

        for (int i = 0; i < n; ++i) {
            lengths[i] = 1; counts[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                   if (lengths[j] >= lengths[i]) {
                       lengths[i] = lengths[j] + 1;
                       counts[i] = counts[j];
                   }
                   else if (lengths[j] + 1 == lengths[i]) {
                       counts[i] += counts[j];
                   }
                }
            }
        }
        int longest = 0, count = 0;
        for (int len : lengths) {
            longest = Math.max(longest, len);
        }
        for (int i = 0; i < n; ++i) {
            if (lengths[i] == longest) {
                count += counts[i];
            }
        }
        return count;
    }
}

买卖股票的最佳时机II

⚡ 贪心

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for(int i = 1; i < prices.length; ++i) {
            if(prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }
}

⚡ 动态规划

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[] dp = new int[n];
        dp[0] = 0;
        for (int i = 1; i < n; ++i) {
            //转移方程
            dp[i] = dp[i - 1] + Math.max(prices[i] - prices[i - 1], 0);
        }
        return dp[n - 1];
    }
}

最大子序和

⚡ 动态规划

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int ans = nums[0];
        dp[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            //dp[i]表示包括以i号数字结尾的字符串的最大值
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            ans = Math.max(dp[i], ans);
        }
        return ans;
    }
}

⚡ 优化掉dp数组

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int lastNum = nums[0];
        int ans = nums[0];
        for (int i = 1; i < n; ++i) {
            lastNum = Math.max(lastNum + nums[i], nums[i]);
            ans = Math.max(lastNum, ans);
        }
        return ans;
    }
}

丑数II

见LeetCode每日打卡-April4月11日

直方图的水量⭐

见LeetCode每日打卡-April4月2日

打家劫舍

⚡ 动态规划

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

打家劫舍 II

见LeetCode每日打卡-April4月15日

2.2 双串问题

最长公共子序列

见LeetCode每日打卡-April4月3日

扰乱字符串🌟

见LeetCode每日打卡-April4月16日

2.3 矩阵问题

不同路径⭐

⚡ 动态规划

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 || j == 0) dp[i][j] = 1;
                else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m-1][n-1];
    }
}
赏

Try and fail, but don't fail to try.