零钱兑换问题

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。

最优子结构

设计搜索的状态，对于每一个剩余金额，搜索一次，求出兑换出这个金额所需要的最少硬币数。
比如有1, 9, 10这三种面额的硬币，凑齐总金额为n的硬币数可以表达为：

  1. opt(n) = min(opt(n-1), opt(n-9), opt(n-10)) + 1

image.png

递推实现

  1. public int coinChange(int[] coins, int amount) {
  2.     int INF = (int) 1e9;
  3.     // opt[n]表示兑换面值为所需要的最小硬币数
  4.     int[] opt = new int[amount + 1];
  5.     opt[0] = 0;
  7.     // 算0到amount之间的每一个i
  8.     for (int i = 1; i <= amount; i++) {
  9.       opt[i] = INF;
  10.       // 枚举coins的面额
  11.       for (int j = 0; j < coins.length; j++) {
  12.         if (i - coins[j] >= 0) {
  13.           // 凑齐i需要的硬币数是opt[i]与 i与coins[j] +1的最小值
  14.           opt[i] = Math.min(opt[i], opt[i - coins[j]] + 1);
  15.         }
  17.         if (opt[amount] >= INF) {
  18.           opt[amount] = -1;
  19.         }
  20.       }
  21.     }
  22.     return opt[amount];
  23.   }

动态规划

  1.   public int coinChange2(int[] coins, int amount) {
  2.     int max = amount + 1;
  3.     // dp[i]表示兑换i金额需要的硬币数
  4.     int[] dp = new int[amount + 1];
  5.     Arrays.fill(dp, max);
  6.     // base case
  7.     dp[0] = 0;
  8.     for (int i = 1; i <= amount; i++) {
  9.       for (int j = 0; j < coins.length; j++) {
  10.         if (coins[j] <= i) {
  11.           // 状态转移方程
  12.           dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
  13.         }
  14.       }
  15.     }
  16.     return dp[amount] > amount ? -1 : dp[amount];
  17.   }

线性动态规划实战

线性动态规划：dp函数的含义的一一确定的。

不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？ 网格中的障碍物和空位置分别用 1 和 0 来表示。

  1. public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  2.       if (obstacleGrid == null || obstacleGrid.length == 0) {
  3.         return 0;
  4.       }
  6.       int m = obstacleGrid.length; // 行
  7.       int n = obstacleGrid[0].length; // 列
  9.       // int[m][n]表示机器人从左上角到[m][n]位置的路径数
  10.       int[][] dp = new int[m][n];
  12.       // dp计算
  13.       for (int i = 0; i < m; i++) {
  14.         for (int j = 0; j < n; j++) {
  15.           // 如果遇到障碍物，那么路径为0
  16.           if (obstacleGrid[i][j] == 1) dp[i][j] = 0;
  17.           // base case,起始位置
  18.           else if (i == 0 && j ==0) dp[i][j] = 1;
  19.           // 填dp表的第一行和第一列
  20.           else if (i == 0) dp[i][j] = dp[i][j-1];
  21.           else if (j == 0) dp[i][j] = dp[i-1][j];
  22.           // 常规情况，向下走或向右走
  23.           else dp[i][j] = dp[i-1][j] + dp[i][j-1];
  24.         }
  25.       }
  26.       return dp[m - 1][n - 1];
  27.     }

最长公共子序列

  1. public int longestCommonSubsequence(String text1, String text2) {
  2.       int m = text1.length();
  3.       int n = text2.length();
  5.       // 为了避免边界条件的讨论，将text1和text2前面分别置为" "
  6.       text1 = " " + text1;
  7.       text2 = " " + text2;
  9.       // dp[i][j]表示text1和text2分别从0位置到i、j位置的公共子序列的长度
  10.       int[][] dp = new int[m + 1][n + 1];
  12.       for (int i = 1; i <= m; i++) {
  13.         for (int j = 1; j <= n; j++) {
  14.           if (text1.charAt(i) == text2.charAt(j)) { // i和j位置字符相同
  15.             dp[i][j] = dp[i - 1][j - 1] + 1;
  16.           } else { // i和j位置的字符不同
  17.             dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
  18.           }
  19.         }
  20.       }
  21.       return dp[m][n];
  22.     }

最长递增子序列

  1. public int lengthOfLIS(int[] nums) {
  2.       int n = nums.length;
  3.       // dp[n]表示从0位置开始到n位置区间数组最长递增子序列的长度
  4.       int[] dp = new int[n];
  5.       Arrays.fill(dp, 1);
  6.       int ans = 1;
  8.       // 求每个位置的i
  9.       for (int i = 1; i < n; i++) {
  10.         // 枚举i前面的数，如果小于i位置的数，那么构成递增结构,可以写状态转移方程
  11.         for (int j = 0; j < i; j++) {
  12.           if (nums[i] > nums[j])
  13.             dp[i] = Math.max(dp[i], dp[j] +1);
  14.         }
  15.         ans = Math.max(ans, dp[i]);
  16.       }
  17.       return ans;
  18.     }

最大子数组和

dp[𝑖] 表示以 𝑖 为结尾的最大子序和， dp [𝑖] = max (dp[ 𝑖 − 1] + 𝑛𝑢𝑚𝑠 [𝑖] , 𝑛𝑢𝑚𝑠[𝑖])

  1. public int maxSubArray(int[] nums) {
  2.       int n = nums.length;
  3.       int[] dp = new int[n];
  4.       dp[0] = nums[0];
  5.       int ans = nums[0];
  7.       // dp[𝑖] 表示以 𝑖 为结尾的最大子序和
  8.       for (int i = 1; i < n; i++) {
  9.         // 如果dp[i-1] + num[i] < num[i],说明dp[i-1] <0,可以舍弃，子数组从位置开始
  10.         dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
  11.         ans = Math.max(ans, dp[i]);
  12.       }
  13.       return ans;
  14.     }

乘积最大子数组

  • 与上面最大子数组和类似，dp[𝑖] 表示以 𝑖 为结尾的最大子序和，但需要注意的是，上面的状态转移方程中：dp[i] = Math.max(dp[i - 1] + nums[i], nums[i])，也说明了当dp[i-1] < 0的时候，dp[i-1]可以不要了，我们只要从nums[i]开始开启一个新数组就可以了。但这个题考虑到dp[i-1]，nums[i]均有可能为负数，所以应该还有一个状态来表示乘积最小的子数组。

    1.   public int maxProduct(int[] nums) {
    2.     int n = nums.length;
    4.     // dp[i]表示从0到位置i乘积最大/最小子数组
    5.     int[] fMax = new int[n];
    6.     int[] fMin = new int[n];
    8.     fMax[0] = nums[0];
    9.     fMin[0] = nums[0];
    10.     int ans = nums[0];
    12.     for (int i = 1; i < n; i++) {
    13.       fMax[i] = Math.max(Math.max(fMax[i - 1] * nums[i], nums[i]), fMin[i - 1] * nums[i]);
    14.       fMin[i] = Math.min(Math.min(fMax[i - 1] * nums[i], nums[i]), fMin[i - 1] * nums[i]);
    15.       ans = Math.max(ans, fMax[i]);
    16.     }
    17.     return ans;
    18.   }

    爬楼梯

    1. public int climbStairs(int n) {
    2.     if (n <=2) return n;
    4.     // dp[n]表示爬n级台阶的方法数
    5.     int[] dp = new int[n+1];
    6.     dp[1] = 1;
    7.     dp[2] = 2;
    9.     for (int i = 3; i <= n; i++) {
    10.       // 每次可以爬一阶或者两阶
    11.       dp[i] = dp[i-1] + dp[i-2];
    12.     }
    13.     return dp[n];
    14.   }

    买卖股票系列问题

    股票问题系列通解)

image.png
image.png

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

  • 这是一个典型的线性动规，由于只会有一次买入和卖出，如果想知道某一天卖出的最大收益，只需要知道0到i之间的最低价格就行了。

    1. // 由于股票只会有一次买卖，想求第i天的最大收益只需要知道第i天之前股票的最低价格就行了
    2.   public int maxProfit(int[] prices) {
    3.     // dp[i]表示在0到i天股票的最低价格
    4.     int n = prices.length;
    5.     int[] dp = new int[n];
    6.     dp[0] = prices[0];
    8.     int ans = 0;
    10.     for (int i = 1; i < n; i++) {
    11.       dp[i] = Math.min(dp[i - 1], prices[i]);
    12.       ans = Math.max(ans, prices[i] - dp[i]);
    13.     }
    14.     return ans;
    15.   }

    122. 买卖股票的最佳时机 II

    image.png

    1. public int maxProfit(int[] prices) {
    2.     // dp[i][j]表示在第i天结束时，持有j(0、1)股股票的最大收益
    3.     int n = prices.length;
    4.     int[][] dp = new int[n][2];
    5.     dp[0][0] = 0;
    6.     dp[0][1] = -prices[0];
    8.     for (int i = 1; i < n; i++) {
    9.       // 决定在i位置是否卖出
    10.       dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
    11.       // 决定在i位置是否买入
    12.       dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    13.     }
    14.     return dp[n - 1][0];
    15.   }

    188. 买卖股票的最佳时机 IV

    给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

image.png
image.png

复杂一些的线性DP题目

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

  1. public int rob(int[] nums) {
  2.       if (nums == null || nums.length == 0) {
  3.         return 0;
  4.       }
  5.       if (nums.length == 1) {
  6.         return nums[0];
  7.       }
  8.       // dp[i]表示偷到第i号房间，所能偷到的最大金额
  9.       int n = nums.length;
  10.       int[] dp = new int[n];
  12.       dp[0] = nums[0];
  13.       dp[1] = Math.max(nums[0], nums[1]);
  15.       for (int i = 2; i < n; i++) {
  16.         // 两个选择：偷当前位置或者不偷当前位置房间，求最大值
  17.         dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  18.       }
  19.       return dp[n - 1];
  20.     }
  • 上面的这种解法是一种朴素的做法，我们也可以套用股票问题中的模板：f(i, j)表示计划偷窃前i座房屋，第i号房间闯入的情况为j（0-未闯入，1-闯入）时的做大收益。

image.png

  1.  public int rob(int[] nums) {
  2.     int n = nums.length;
  3.     // dp[i][j]表示在进入或不进去i号房间时的最大收益
  4.     int[][] dp = new int[n][2];
  5.     dp[0][0] = 0;
  6.     dp[0][1] = nums[0];
  8.     for (int i = 1; i < n; i++) {
  9.       // 不进入i号房间：即进入i-1和不进入i-1房间的最大值
  10.       dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
  11.       // 进入i号房间：不进入i-1房间 + nums[i]
  12.       dp[i][1] = dp[i - 1][0] + nums[i];
  13.     }
  14.     return Math.max(dp[n-1][0], dp[n-1][1]);
  15.   }

213. 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

  • 滚动型带环的dp问题，使用两次dp来计算。

    1. public int rob(int[] nums) {
    2.     if (nums == null || nums.length == 0)
    3.       return 0;
    4.     if (nums.length == 1)
    5.       return nums[0];
    6.     if (nums.length == 2)
    7.       return Math.max(nums[0], nums[1]);
    9.     int n = nums.length;
    10.     // 偷第一家，不偷最后一家的最大利益
    11.     int[] dp1 = new int[n - 1];
    12.     // 偷最后一家，不偷第一家的最大利益
    13.     int[] dp2 = new int[n];
    15.     dp1[0] = nums[0];
    16.     dp1[1] = nums[0];
    18.     for (int i = 2; i < n - 1; i++) {
    19.       // 当前位置两种选择：偷与不偷
    20.       dp1[i] = Math.max(dp1[i - 2] + nums[i], dp1[i - 1]);
    21.     }
    23.     dp2[0] = 0;
    24.     dp2[1] = nums[1];
    26.     for (int i = 2; i < n; i++) {
    27.       dp2[i] = Math.max(dp2[i - 2] + nums[i], dp2[i - 1]);
    28.     }
    30.     return Math.max(dp1[n - 2], dp2[n - 1]);
    31.   }

    72. 编辑距离

    给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作：

    • 插入一个字符
    • 删除一个字符
    • 替换一个字符

  • dp[i，j]表示将word1[1…i]变为word2[1…j]的编辑距离。

image.png

  1. public int minDistance(String word1, String word2) {
  2.       int n = word1.length();
  3.       int m = word2.length();
  5.       word1 = " " + word1;
  6.       word2 = " " + word2;
  8.       // dp[i,j]表示将word1[1...i]变为word2[1...j]的编辑距离。
  9.       int[][] dp = new int[n + 1][m + 1];
  10.       // word1变为空字符串或者空字符串变为word2
  11.       for (int i = 0; i <= n; i++) dp[i][0] = i;
  12.       for (int i = 0; i <= m; i++) dp[0][i] = i;
  14.       for (int i = 1; i <= n; i++) {
  15.         for (int j = 1; j <= m; j++) {
  16.           // 插入、删除、替换(不变)
  17.           int step = word1.charAt(i) == word2.charAt(j) ? 0 : 1;
  18.           dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), 
  19.                               dp[i - 1][j - 1] + step);
  20.         }
  21.       }
  22.       return dp[n][m];
  23.     }