爬楼梯问题

70. 爬楼梯

  1. class Solution {
  2.     public int climbStairs(int n) {
  3.         if(n == 1 || n == 2) {
  4.             return n;
  5.         }
  6.         int first = 1, second = 2;
  7.         for(int i = 3; i <= n; i++) {
  8.             int t = second;
  9.             second = first + second;
  10.             first = t;
  11.         }
  12.         return second;
  13.     }
  14. }

322. 零钱兑换

  1. class Solution {
  2.     public int coinChange(int[] coins, int amount) {
  3.         // 定义状态：
  4.         // dp[i][j] 表示第 i 个面额的硬币决策完后，金额能达到 j 的最少硬币个数
  5.         // 状态转移方程为：dp[i][j] = min(dp[i][j - (0 ~ k) * coins])
  6.         int n = coins.length;
  7.         int[][] dp = new int[n][amount + 1];
  8.         // 初始化标识符
  9.         for(int i = 0; i < n; i++){
  10.             Arrays.fill(dp[i], Integer.MAX_VALUE);
  11.         }
  12.         // 初始化第一层
  13.         for(int i = 0; i  <=  amount / coins[0]; i++) {
  14.             dp[0][i * coins[0]] = i;
  15.         }
  17.         for(int i = 1; i < n; i++) {
  18.             for(int j = 0; j <= amount; j++) {
  19.                 int k = j / coins[i];
  20.                 for(int c = 0; c <= k; c++) {
  21.                     if(j >= c * coins[i] && dp[i - 1][j - c * coins[i]] != Integer.MAX_VALUE) {
  22.                         dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - c * coins[i]] + c);
  23.                     }
  24.                 } 
  25.             }
  26.         }
  27.         return dp[n - 1][amount] == Integer.MAX_VALUE ? -1 : dp[n - 1][amount];
  28.     }
  29. }

518. 零钱兑换 II

  1. class Solution {
  2.     public int coinChange(int[] coins, int amount) {
  3.         // 定义状态：
  4.         // dp[i][j] 表示第 i 个面额的硬币决策完后，金额能达到 j 的最少硬币个数
  5.         // 状态转移方程为：dp[i][j] = min(dp[i][j - (0 ~ k) * coins])
  6.         int n = coins.length;
  7.         int[][] dp = new int[n][amount + 1];
  8.         // 初始化标识符
  9.         for(int i = 0; i < n; i++){
  10.             Arrays.fill(dp[i], Integer.MAX_VALUE);
  11.         }
  12.         // 初始化第一层
  13.         for(int i = 0; i  <=  amount / coins[0]; i++) {
  14.             dp[0][i * coins[0]] = i;
  15.         }
  17.         for(int i = 1; i < n; i++) {
  18.             for(int j = 0; j <= amount; j++) {
  19.                 int k = j / coins[i];
  20.                 for(int c = 0; c <= k; c++) {
  21.                     if(j >= c * coins[i] && dp[i - 1][j - c * coins[i]] != Integer.MAX_VALUE) {
  22.                         dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - c * coins[i]] + c);
  23.                     }
  24.                 } 
  25.             }
  26.         }
  27.         return dp[n - 1][amount] == Integer.MAX_VALUE ? -1 : dp[n - 1][amount];
  28.     }
  29. }


剑指 Offer 14- I. 剪绳子

  1. class Solution {
  2.     public int cuttingRope(int n) {
  3.         if(n < 2) {
  4.             return 1;
  5.         }
  6.         if(n == 2 || n == 3) {
  7.             return n - 1;
  8.         }
  9.         int[] dp = new int[n + 1];
  10.         dp[1] = 1;
  11.         dp[2] = 2;
  12.         dp[3] = 3;
  13.         for(int i = 4; i <= n; i++) {
  14.             int max = Integer.MIN_VALUE;
  15.             int low = (i & 1) == 1 ? i / 2 + 1 : i / 2;
  16.             for(int j = i - 1; j >= low; j--) {
  17.                 max = Math.max(max, dp[j] * dp[i - j]);
  18.             }
  19.             dp[i] = max;
  20.         }
  21.         return dp[n];
  22.     }
  23. }

剑指 Offer 46. 把数字翻译成字符串

  1. class Solution {
  2.     public int translateNum(int num) {
  3.         // 定义状态：dp[i] 表示当前 i 长度的数字存在多少种解法
  4.         // dp[i] 状态只能从上1个数字或上两个数字演化而来，前提是两数字之和不能超过25
  5.         // 状态转移方程：
  6.         // 当两数字之和超过25 dp[i] = dp[i - 1] 
  7.         // 当两数字之和不能超过25 dp[i] = dp[i - 1] + dp[i - 2]
  8.         List<Integer> list = new ArrayList<>();
  9.         while(num != 0) {
  10.             list.add(num % 10);
  11.             num /= 10;
  12.         }
  13.         int size = list.size();
  14.         int[] array = new int[size];
  15.         for(int i = 0; i < size; i++) {
  16.             array[i] = list.get(size - 1 - i);
  17.         }
  18.         int[] dp = new int[size + 1];
  19.         dp[0] = 1;
  20.         for(int i = 1; i <= size; i++) {
  21.             dp[i] += dp[i - 1];
  22.             if(i >=2 && valid(array[i - 2], array[i - 1])) {
  23.                 dp[i] += dp[i - 2];
  24.             }
  25.         }
  26.         return dp[size];
  27.     }
  29.     private boolean valid(int a, int b) {
  30.         if(a == 1) {
  31.             return true;
  32.         }
  33.         if(a == 2 && b <= 5) {
  34.             return true;
  35.         }
  36.         return false;
  37.     }
  38. }

139. 单词拆分

  1. class Solution {
  2.     public boolean wordBreak(String s, List<String> wordDict) {
  3.         // 定义状态：
  4.         // dp[i] 表示当前 i 长度的字符串能否被空格拆分为一个或多个在字典 wordDict 中出现的单词
  5.         // 假设字典 wordDict 中word1、word2、word3能跟 s[0~i - 1]的后缀匹配起来，那么说明到达 i 这个状态只能从 i - len1，i-len2，i-len3 这三个状态转移过来
  6.         // 状态转移方程：dp[i] = dp[i - len1] || dp[i - len2] || dp[i - len3]
  7.         int l = s.length();
  8.         boolean[] dp = new boolean[l + 1];
  9.         dp[0] = true;
  10.         for(int i = 0; i <= l; i++) {
  11.             for(String word : wordDict) {
  12.                 int len = word.length();
  13.                 int start = i -len;
  14.                 if(start >= 0 && s.startsWith(word, start) && dp[i - len]) {
  15.                     dp[i] = true;
  16.                     break;
  17.                 }
  18.             }
  19.         }
  20.         return dp[l];
  21.     }
  22. }

匹配问题

1143. 最长公共子序列

  1. class Solution {
  2.     public int longestCommonSubsequence(String text1, String text2) {
  3.         // 定义状态：dp[i][j] 表示长度为 i 的字符串 s1 和 长度为 j 的字符串 s2 之间的最长公共子序列
  4.         // 当 text1[i] == text2[j] 时，相当于两字符串都多了一个相同的字符，则 dp[i][j] = dp[i - 1][j - 1] + 1
  5.         // 当 text1[i] != text2[j] 时，那么 dp[i][j] 的状态只能从 dp[i - 1][j] 或者 dp[i][j - 1] 处到达，那么 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
  6.         int m = text1.length(), n = text2.length();
  7.         int[][] dp = new int[m + 1][n + 1];
  8.         for(int i = 1; i <= m; i++) {
  9.             char c = text1.charAt(i - 1);
  10.             for(int j = 1; j <= n; j++) {
  11.                 if(c == text2.charAt(j - 1)) {
  12.                     dp[i][j] = dp[i - 1][j - 1] + 1;
  13.                 } else {
  14.                     dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
  15.                 }
  16.             }
  17.         }
  18.         return dp[m][n]; 
  19.     }
  20. }

72. 编辑距离

  1. class Solution {
  2.     public int minDistance(String word1, String word2) {
  3.         // 定义状态：dp[i][j] 表示长度为 i 的 word1 转换成 长度为 j 的 word2 所使用的最少操作数
  4.         // 当 word1[i] = word2[j]，dp[i][j] = dp[i - 1][j - 1]
  5.         // 当word1[i] != word2[j]：
  6.         // 如果是替换字符：dp[i - 1][j - 1]
  7.         // 如果是插入一个字符： dp[i][j] = dp[i][j - 1] + 1;
  8.         // 如果是删除一个字符 dp[i][j] = dp[i - 1][j] + 1;
  9.         // dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
  11.         int m = word1.length(), n = word2.length();
  13.         if(m * n == 0) {
  14.             return m + n;
  15.         }
  16.         int[][] dp = new int[m + 1][n + 1];
  17.         for(int i = 1; i <= m; i++) {
  18.             dp[i][0] = i;
  19.         }
  20.         for(int i = 1; i <= n; i++) {
  21.             dp[0][i] = i;
  22.         }
  24.         for(int i = 1; i <= m; i++) {
  25.             for(int j = 1; j <= n; j++) {
  26.                 if(word1.charAt(i - 1) == word2.charAt(j - 1)) {
  27.                     dp[i][j] = dp[i - 1][j - 1];
  28.                 } else {
  29.                     dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
  30.                 }
  31.             }
  32.         }
  33.         return dp[m][n];
  34.     }
  35. }

其他

437. 路径总和 III (树形DP)

  1. class Solution {
  2.     private int count = 0;
  4.     public int pathSum(TreeNode root, int targetSum) {
  5.         // 树形DP，状态从左右子树转移而来，利用DFS来做
  6.         // 用 Map 来存储以每个节点作为root节点的路径情况，key为路径和，value为路径条数
  7.         dfs(root, targetSum);
  8.         return count;
  9.     }
  11.     private Map<Integer, Integer> dfs(TreeNode node, int targetSum) {
  12.         if(node == null) {
  13.             return new HashMap<Integer, Integer>();
  14.         }
  16.         Map<Integer, Integer> nodeMap = new HashMap();
  17.         nodeMap.put(node.val, 1); 
  18.         Map<Integer, Integer> leftNodeMap = dfs(node.left, targetSum);
  19.         Map<Integer, Integer> rightNodeMap = dfs(node.right, targetSum);
  21.         // 遍历左子节点的Map
  22.         for(Map.Entry<Integer, Integer> entry : leftNodeMap.entrySet()) {
  23.             Integer newKey = entry.getKey() + node.val;
  24.             Integer newValue = entry.getValue();
  25.             if(nodeMap.containsKey(newKey)) {
  26.                 newValue += nodeMap.get(newKey);
  27.             }
  28.             nodeMap.put(newKey, newValue);
  29.         }
  31.         // 遍历右子节点的Map
  32.         for(Map.Entry<Integer, Integer> entry : rightNodeMap.entrySet()) {
  33.             Integer newKey = entry.getKey() + node.val;
  34.             Integer newValue = entry.getValue();
  35.             if(nodeMap.containsKey(newKey)) {
  36.                 newValue += nodeMap.get(newKey);
  37.             }
  38.             nodeMap.put(newKey, newValue);
  39.         }
  41.         // 遍历当前节点的 Map
  42.         for(Map.Entry<Integer, Integer> entry : nodeMap.entrySet()){
  43.             if(entry.getKey() == targetSum) {
  44.                 count += entry.getValue();
  45.             }
  46.         }
  48.         return nodeMap;
  49.     }
  50. }

300. 最长递增子序列

  1. class Solution {
  2.     public int lengthOfLIS(int[] nums) {
  3.         // 定义状态：
  4.         // dp[i] 表示以 nums[i] 整数结尾的最长严格递增子序列的长度
  5.         // 当nums[i] > nums[j]时，dp[i] = max(dp[j]) + 1 （j 的取值范围为 0 ~ j）
  6.         // 状态转移方程式为： dp[i] = max(dp[j]) + 1; nums[i] > nums[j] && j < i
  7.         // 那么整个数组中，最长严格递增的子序列的长度为：max(dp[0] ~ dp[i])
  8.         int n = nums.length;
  9.         int[] dp = new int[n];
  10.         dp[0] = 1;
  11.         int max = Integer.MIN_VALUE;
  12.         for(int i = 1; i < n; i++) {
  13.             for(int j = i - 1; j >= 0; j--) {
  14.                 if(nums[i] > nums[j]) {
  15.                     dp[i] = Math.max(dp[i], dp[j]);
  16.                 }
  17.             }
  18.             dp[i]++;
  19.             max = Math.max(max, dp[i]);
  20.         }
  21.         return Math.max(max, dp[0]);
  22.     }
  23. }