【LeetCode】動態規劃入門（專項打卡21天合集）

【LeetCode】動態規劃入門（專項打卡21天合集）

下圖為證

Day1

斐波拉契數

509. 斐波那契數

class Solution {
    public int fib(int n) {
        int[] dp = new int[31];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

第 N 個泰波那契數

1137. 第 N 個泰波那契數

class Solution {
    public int tribonacci(int n) {
        int[] dp = new int[38];
        dp[1] = dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        return dp[n];
    }
}

Day2

爬樓梯

70. 爬樓梯

class Solution {
    public int climbStairs(int n) {
        if (n < 3) return n;
        int cur = 2, pre = 1;
        for (int i = 3; i <= n; i++) {
            int temp = cur;
            cur += pre;
            pre = temp;
        }
        return cur;
    }
}

使用最小花費爬樓梯

746. 使用最小花費爬樓梯

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

Day3

打家劫舍

198. 打家劫舍

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

打家劫舍 II

213. 打家劫舍 II

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int val1 = rob1(nums);
        reverse(nums);
        int val2 = rob1(nums);
        return Math.max(val1, val2);
    }

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

    private void reverse(int[] nums) {
        int n = nums.length, i = 0;
        while (i < n / 2) {
            int t = nums[i];
            nums[i] = nums[n - i - 1];
            nums[n - i - 1] = t;
            i++;
        }
    }
}

洗掉并獲得點數

740. 洗掉并獲得點數

class Solution {
    public int deleteAndEarn(int[] nums) {
        int n = 10000;
        int[] mark = new int[n + 1];
        for (int num : nums) mark[num] += num;
        int[] dp = new int[n + 2];
        dp[1] = mark[0];
        for (int i = 1; i < n + 1; i++) {
            dp[i + 1] = Math.max(dp[i], dp[i - 1] + mark[i]);
        }
        return dp[n + 1];
    }
}

Day4

跳躍游戲

55. 跳躍游戲

前向遍歷

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

后向遍歷

class Solution {
    public boolean canJump(int[] nums) {
        if(nums == null || nums.length < 2) return true;
        int le = nums.length - 1;
        for(int i = nums.length - 2; i >= 0; i--) {
            if(i + nums[i] >= le) le = i;
        }
        return le == 0;
    }
}

跳躍游戲 II

45. 跳躍游戲 II

動態規劃法

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = 1; j <= nums[i] && i + j < n; j++) {
                dp[i + j] = dp[i + j] == 0 ? dp[i] + 1 : Math.min(dp[i + j], dp[i] + 1);
            }
        }
        return dp[n - 1];
    }
}

貪心法

class Solution {
    public int jump(int[] nums) {
        int steps = 0;
        int reach = 0, nextreach = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            nextreach = Math.max(nextreach, i + nums[i]);
            if (reach == i) {
                reach = nextreach;
                steps++;
            }
        }
        return steps;
    }
}

Day5

最大子序和

53. 最大子序和

class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0], cur = nums[0];
        for (int i = 1; i < nums.length; i++) {
            cur = cur > 0 ? cur + nums[i] : nums[i];
            res = Math.max(res, cur);
        }
        return res;
    }
}

環形子陣列的最大和

918. 環形子陣列的最大和

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int max, min, curMax, curMin, sum;
        max = min = curMax = curMin = sum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sum += nums[i];
            curMax = curMax > 0 ? curMax + nums[i] : nums[i];
            max = Math.max(max, curMax);
            curMin = curMin < 0 ? curMin + nums[i] : nums[i];
            min = Math.min(min, curMin);
        }
        return max < 0 ? max : Math.max(max, sum - min);
    }
}

Day6

乘積最大子陣列

152. 乘積最大子陣列

class Solution {
    public int maxProduct(int[] nums) {
       int res, max, min;
       res = max = min = nums[0];
       for (int i = 1; i < nums.length; i++) {
           int mx = max, mn = min;
           max = Math.max(mx * nums[i], Math.max(mn * nums[i], nums[i]));
           min = Math.min(mx * nums[i], Math.min(mn * nums[i], nums[i]));
           res = Math.max(res, max);
       } 
       return res;
    }
}

乘積為正數的最長子陣列長度

1567. 乘積為正數的最長子陣列長度

class Solution {
    public int getMaxLen(int[] nums) {
        int res = 0, p = 0, q = 0;
        for (int num : nums) {
            if (num == 0) {
                p = q = 0;    //乘積為正負的長度
            } else {
                if (num > 0) {
                    p++;
                    if (q > 0) q++;
                } else {
                    int t = p;
                    p = q;
                    q = t;
                    q++;
                    if (p > 0) p++;
                }
            }
            res = Math.max(res, p);
        }
        return res;
    }
}

Day7

最佳觀光組合

1014. 最佳觀光組合

class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int res = 0, leftMax = 0;
        for (int i = 0; i < values.length; i++) {
            res = Math.max(res, leftMax + values[i] - i);
            leftMax = Math.max(leftMax, values[i] + i);
        }
        return res;
    }
}

買賣股票的最佳時機

121. 買賣股票的最佳時機

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0, minPrice = 10001;
        for (int price : prices) {
            minPrice = Math.min(minPrice, price);
            profit = Math.max(profit, price - minPrice);
        }
        return profit;
    }
}

買賣股票的最佳時機 II

122. 買賣股票的最佳時機 II

方法一：動態規劃法

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];  //0不持有1持有
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[n - 1][0];
    }
}

方法二：貪心法

class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        for (int i = 1; i < prices.length; i++) {
            res += Math.max(0, prices[i] - prices[i - 1]);
        }
        return res;
    }
}

Day8

最佳買賣股票時機含冷凍期

309. 最佳買賣股票時機含冷凍期

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n + 2][2];  //0不持有1持有
        dp[0][1] = dp[1][1] = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            dp[i + 2][0] = Math.max(dp[i + 1][0], dp[i + 1][1] + prices[i]);
            dp[i + 2][1] = Math.max(dp[i + 1][1], dp[i][0] - prices[i]);
        }
        return dp[n + 1][0];
    }
}

買賣股票的最佳時機含手續費

714. 買賣股票的最佳時機含手續費

方法一：

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

方法二：

class Solution {
    public int maxProfit(int[] prices, int fee) {
        if (prices.length < 2) return 0;
        int buy = -prices[0], sell = 0;
        for (int i = 1; i < prices.length; i++) {
            buy = Math.max(buy, sell - prices[i]);
            sell = Math.max(sell, buy + prices[i] - fee);
        }
        return sell;
    }
}

Day9

單詞拆分

139. 單詞拆分

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length(), len = 0;
        Set<String> set = new HashSet<>();
        for (String word : wordDict) {
            set.add(word);
            len = Math.max(len, word.length());
        }
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = Math.max(0, i - len); j < i; j++) {
                if (dp[j] && set.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}

接雨水

42. 接雨水

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length < 3) return 0;
        int res = 0;
        int L = 1, R = height.length - 2;
        int leftMax = height[0], rightMax = height[height.length - 1];
        while(L <= R) {
            if (leftMax < rightMax) {
                res += Math.max(0, leftMax - height[L]);
                leftMax = Math.max(leftMax, height[L++]);
            } else {
                res += Math.max(0, rightMax - height[R]);
                rightMax = Math.max(rightMax, height[R--]);
            }
        }
        return res;
    }
}

Day10

等引數列劃分

413. 等引數列劃分

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

優化版

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        if (nums.length < 3) return 0;
        int res = 0, pre = 0;
        for (int i = 2; i < nums.length; i++) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                pre += 1;
                res += pre;
            } else {
                pre = 0;
            }
        }
        return res;
    }
}

解碼方法

91. 解碼方法

class Solution {
    public int numDecodings(String s) {
        if (s.charAt(0) == '0') return 0;
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            dp[i + 1] = s.charAt(i) == '0' ? 0 : dp[i];
            if (i > 0 && (s.charAt(i - 1) == '1' || s.charAt(i - 1) == '2' && s.charAt(i) < '7')) {
                dp[i + 1] += dp[i - 1];
            }
        }
        return dp[n];
    }
}

Day11

丑數 II

264. 丑數 II

class Solution {
    public int nthUglyNumber(int n) {
        int two, three, five;
        two = three = five = 0;
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = Math.min(dp[two] * 2, Math.min(dp[three] * 3, dp[five] * 5));
            if (dp[i] == dp[two] * 2) two++;
            if (dp[i] == dp[three] * 3) three++;
            if (dp[i] == dp[five] * 5) five++;
        }
        return dp[n - 1];
    }
}

不同的二叉搜索樹

96. 不同的二叉搜索樹

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}

Day12

楊輝三角

118. 楊輝三角

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        if (numRows == 0) return res;
        List<Integer> temp = new ArrayList<>();
        temp.add(1);
        res.add(temp);
        for (int i = 1; i < numRows; i++) {
            List<Integer> list = new ArrayList<>();
            temp = res.get(i - 1);
            for (int j = 0; j <= i; j++) {
                if (j == 0 || i == j) {
                    list.add(1);
                } else {
                    list.add(temp.get(j - 1) + temp.get(j));
                }
            }
            res.add(list);
        }
        return res;
    }
}

楊輝三角 II

119. 楊輝三角 II

class Solution {
    public List<Integer> getRow(int rowIndex) {
        Integer[] dp = new Integer[rowIndex + 1];
        Arrays.fill(dp, 1);
        for (int i = 1; i <= rowIndex; i++) {
            for (int j = i - 1; j > 0; j--) {
                dp[j] = dp[j] + dp[j - 1];
            }
        }
        List<Integer> res = Arrays.asList(dp);
        return res;
    }
}

Day13

下降路徑最小和

931. 下降路徑最小和

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int minVal;
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                minVal = 10000;
                if (j > 0) minVal = Math.min(minVal, matrix[i - 1][j - 1]);
                if (j < n - 1) minVal = Math.min(minVal, matrix[i - 1][j + 1]);
                minVal = Math.min(minVal, matrix[i - 1][j]);
                matrix[i][j] += minVal;
            }
        }
        int res = 10000;
        for (int i = 0; i < n; i++) {
            res = Math.min(res, matrix[m - 1][i]);
        }
        return res;
    }
}

三角形最小路徑和

120. 三角形最小路徑和

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        for(int i = triangle.size() - 2; i >= 0; i--) {
            for(int j = 0; j < triangle.get(i).size(); j++) {
                triangle.get(i).set(j, Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)) + triangle.get(i).get(j));
            }
        }
        return triangle.get(0).get(0);
    }
}

Day14

矩陣區域和

1314. 矩陣區域和

class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;
        int[][] pre = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j] + mat[i][j];
            }
        }
        int[][] ans = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int to = Math.max(0, i - k);
                int bo = Math.min(m - 1, i + k) + 1;
                int le = Math.max(0, j - k);
                int ri = Math.min(n - 1, j + k) + 1;
                ans[i][j] = pre[bo][ri] - pre[to][ri] - pre[bo][le] + pre[to][le];
            }
        }
        return ans;
    }
}

二維區域和檢索 - 矩陣不可變

304. 二維區域和檢索 - 矩陣不可變

class NumMatrix {
    int[][] pre;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        pre = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                pre[i + 1][j + 1] = pre[i][j + 1] + pre[i + 1][j] - pre[i][j] + matrix[i][j];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        row2 += 1;
        col2 += 1;
        return pre[row2][col2] - pre[row2][col1] - pre[row1][col2] + pre[row1][col1];
    }
}

Day15

不同路徑

62. 不同路徑

方法一：動態規劃

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];
    }
}

方法二：組合

class Solution {
    public int uniquePaths(int m, int n) {
        int C = m + n - 2;
        int K = (m > n ? n : m) - 1;
        double res = 1;
        for (int i = 1; i <= K; i++) {
            res = res * (C - i + 1) / i;
        }
        return (int)res;
    }
}

不同路徑 II

63. 不同路徑 II

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[] dp = new int[n];
        dp[0] = obstacleGrid[0][0] == 0 ? 1: 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                    continue;
                }
                if (j >= 1 && obstacleGrid[i][j - 1] == 0) {
                    dp[j] += dp[j - 1];
                }
            }
        }
        return dp[n - 1];
    }
}

Day16

最小路徑和

64. 最小路徑和

class Solution {
    public int minPathSum(int[][] grid) {
        int r = grid.length, c = grid[0].length;
        int[] dp = new int[c];
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (i == 0 && j > 0) {
                    dp[j] = dp[j - 1] + grid[i][j];
                } else if (j == 0) {
                    dp[j] += grid[i][j];
                } else {
                    dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
                }
            }
        }
        return dp[c - 1];
    }
}

最大正方形

221. 最大正方形

class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m + 1][n + 1];
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    dp[i + 1][j + 1] = 1 + Math.min(dp[i][j], Math.min(dp[i + 1][j], dp[i][j + 1]));
                    res = Math.max(res, dp[i + 1][j + 1]);
                }
            }
        }
        return res * res;
    }
}

Day17

最長回文子串

5. 最長回文子串

方法一：動態規劃

class Solution {
    public String longestPalindrome(String s) {
        if (s.length() < 2) return s;
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) dp[i][i] = true;
        int begin = 0, maxLen = 1;
        for (int L = 2; L <= n; L++) {
            for (int i = 0; i < n; i++) {
                int j = L + i - 1;
                if (j >= n) break;
                if (s.charAt(i) != s.charAt(j)) {
                    dp[i][j] = false;
                } else {
                    if (j - i + 1 < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j] && j - i + 1 > maxLen) {
                    begin = i;
                    maxLen = j - i + 1;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}

方法二：中心擴展法

class Solution {
    public String longestPalindrome(String s) {
        //中心擴展法
        int start = 0, maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCentor(s, i, i);
            int len2 = expandAroundCentor(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > maxLen) {
                start = i - (len - 1) / 2;
                maxLen = len;
            }
        }
        return s.substring(start, start + maxLen);
    }

    private int expandAroundCentor(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

最長回文子序列

516. 最長回文子序列

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n + 1][n + 1];
        //最長公共子序列
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                char a = s.charAt(i);
                char b = s.charAt(n - j - 1);
                if (a == b) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                } else {
                    dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]);
                }
            }
        }
        return dp[n][n];
    }
}

Day18

最長遞增子序列

300. 最長遞增子序列

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int k = 0;
        for (int num : nums) {
            if (k == 0 || num > dp[k - 1]) {
                dp[k++] = num;
            } else {
                int index = binarySearch(dp, k - 1, num);
                dp[index] = num;
            }
        }
        return k;
    }

    private int binarySearch(int[] nums, int k, int x) {
        int lo = 0, ri = k;
        while (lo <= ri) {
            int mid = lo + (ri - lo) / 2;
            if (x == nums[mid]) {
                return mid;
            } else if (x < nums[mid]) {
                ri = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

擺動序列

376. 擺動序列

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 2) return nums.length;
        int up = 1, down = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                up = down + 1;
            } else if (nums[i] < nums[i - 1]) {
                down = up + 1;
            }
        }
        return Math.max(up, down);
    }
}

Day19

判斷子序列

392. 判斷子序列

class Solution {
    public boolean isSubsequence(String s, String t) {
        if (s.equals("")) return true;
        int k = 0;
        for (char c : t.toCharArray()) {
            if (k < s.length() && c == s.charAt(k)) {
                if (++k == s.length()) return true;
            }
        }
        return false;
    }
}

最長公共子序列

1143. 最長公共子序列

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n1 = text1.length(), n2 = text2.length();
        int[][] dp = new int[n1 + 1][n2 + 2];
        for (int i = 0; i < n1; i++) {
            for (int j = 0; j < n2; j++) {
                if (text1.charAt(i) == text2.charAt(j)) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                } else {
                    dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]);
                }
            }
        }
        return dp[n1][n2];
    }
}

編輯距離

72. 編輯距離

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] cost = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) cost[i][0] = i;
        for (int j = 0; j <= n; j++) cost[0][j] = j;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (word1.charAt(i) == word2.charAt(j)) {
                    cost[i + 1][j + 1] = cost[i][j];
                } else {
                    cost[i + 1][j + 1] = 1 + Math.min(cost[i][j], Math.min(cost[i][j + 1], cost[i + 1][j]));
                }
            }
        }
        return cost[m][n];
    }
}

Day20

零錢兌換

322. 零錢兌換

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 0; i <= amount; i++) {
            for (int coin : coins) {
                if (i >= coin) dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

零錢兌換 II

518. 零錢兌換 II

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = 0; i <= amount; i++) {
                if (i + coin <= amount) {
                    dp[i + coin] += dp[i];
                }
            }
        }
        return dp[amount];
    }
}

Day21

組合總和 Ⅳ

377. 組合總和 Ⅳ

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (i - num >= 0) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
}

整數拆分

343. 整數拆分

方法一：動態規劃

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = i - 1; j >= 1; j--) {
                dp[i] = Math.max(dp[i], Math.max(dp[j] * (i - j), j * (i - j)));
            }
        }
        return dp[n];
    }
}

方法二：最佳因子是e，所以整數首選3，后選2

class Solution {
    public int integerBreak(int n) {
        //首選3，后選2
        if (n <= 3) return n - 1;
        if (n % 3 == 0) {
            return (int)(Math.pow(3, n / 3));
        } else if (n % 3 == 1) {
            return (int)(Math.pow(3, n / 3 - 1)) * 4;
        } else {
            return (int)(Math.pow(3, n / 3)) * 2; 
        }
    }
}

完全平方數

279. 完全平方數

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        int e = (int)Math.sqrt(n);
        Arrays.fill(dp, n);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 1; j * j <= n; j++) {
                if (i + j * j <= n) {
                    dp[i + j * j] = Math.min(dp[i + j * j], dp[i] + 1);
                }
            }
        }
        return dp[n];
    }
}

21天的煎熬，終于結束啦！😄