菜鸡的原地踏步史03(◐‿◑)

每日一念
改掉自己想到哪写哪的坏习惯

一维动态规划
爬楼梯

class Solution {
    /**
        dp[i] 爬到第i个台阶有dp[i]种爬法
        dp[i] - dp[i - 1] + 1 & dp[i - 2] + 2
     */
    public int climbStairs(int n) {
        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];
        }
        return dp[n];
    }
}

杨辉三角

class Solution {
    /**
        res.get(i)表示第i层的数组
        首尾设置为1
        res.get(i).get(j) = res.get(i - 1).get(j - 1) + res.get(i - 1).get(j)
     */

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList();
        List<Integer> path = new ArrayList();
        for(int i = 0; i < numRows; i++) {
            for(int j = 0; j <= i; j++) {
                if(j == 0 || j == i) {
                    path.add(1);
                }
                else {
                    path.add(0);
                }
            }
            res.add(path);
            path = new ArrayList();
        }
        for(int i = 2; i < res.size(); i++) {
            for(int j = 1; j < res.get(i).size() - 1; j++) {
                int val = res.get(i - 1).get(j - 1) + res.get(i - 1).get(j);
                res.get(i).set(j, val);
                // System.out.println(res.get(i).get(j));
            }
        }
        return res;
    }
}

打家劫舍

class Solution {
    /**
        dp[i]表示第i家能偷到的最高金额
        dp[i] -- dp[i - 1], dp[i - 2] + nums[i - 1]
     */
    // dp[nums.length]
    public int rob(int[] nums) {
        if(nums.length == 0) {
            return 0;
        }
        if(nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = 0;
        dp[1] = nums[0];
        for(int i = 2; i < dp.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return Math.max(dp[nums.length - 1], dp[nums.length - 2] + nums[nums.length - 1]);
    }
    // dp[nums.length + 1]
    public int rob(int[] nums) {
        if(nums.length == 0) {
            return 0;
        }
        if(nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = 0;
        dp[1] = nums[0];
        for(int i = 2; i < dp.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return Math.max(dp[nums.length - 1], dp[nums.length - 2] + nums[nums.length - 1]);
    }
}

完全平方数

class Solution {
    /**
        dp[i] 组成和为i的完全平方数最少数量 -- dp[i - j *j]
        从 < i 的第一个完全平方数开始找
        dp数组需要的最长长度为n + 1
        3 = 1 + 1 + 1 全1组成
     */
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, n);
        dp[0] = 0;
        for(int i = 0; i <= n; i++){
            for(int j = 0; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j *j] + 1);
            }
        }
        return dp[n];
    }
}

零钱兑换

class Solution {
    /**
        dp[i] 面值为i的零钱最少可以兑换的硬币数
        不可达值设置成amount + 1
     */
    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 < dp.length; i++) {
            for(int coin: coins) {
                if(i >= coin) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
                else {
                    continue;
                }
            }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
}

    /**
        不可达值设置成-1
     */
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, -1); // 不可达值
        dp[0] = 0;
        for(int i = 0; i < dp.length; i++) {
            for(int coin: coins) {
                if(i == coin) {
                    dp[i] = 1;
                }
                else if(i > coin) {
                    if(dp[i - coin] == -1) {
                        continue;
                    }
                    else {
                        if(dp[i] == -1) {
                            dp[i] = dp[i - coin] + 1;
                        }
                        else {
                            dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                        }
                    }
                    
                }
            }
        }
        return dp[amount];
    }
}

单词拆分

class Solution {
    /**
        dp[i] 表示前i个字符的组合，可以被字典拼接成
        boolean类型的数组
        dp[s.len + 1]
        dp[j]  + substring(j, i) -- 在word里面

     */
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> map = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for(int i = 1; i < dp.length; i++) {
            for(int j = 0; j < i; j++) {
                if(dp[j] && map.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

最长递增子序列

class Solution {
    /**
        dp[i] 表示元素i结束的最长子序列
     */
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        for(int i = 1; i < dp.length; i++) {
            for(int j = 0; j < i; j++) {
                if(nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int maxlen = Integer.MIN_VALUE;
        for(int i = 0; i < dp.length; i++) {
            if(dp[i] > maxlen) {
                maxlen = dp[i];
            }
        }
        return maxlen;
    }
}

乘积最大子数组

分割等和子集

class Solution {
    /**
        boolean dp[i] 前i个数字是否存在子集和为i
     */
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if(sum % 2 != 0) {
            return false;
        }
        int mid = sum/2;
        boolean[] dp = new boolean[mid + 1];
        dp[0] = true;
        for(int i = 1; i < nums.length; i++) {
            for(int j = dp.length - 1; j >= nums[i - 1]; j--) {
                if(dp[j - nums[i - 1]]) {
                    dp[j] = true;
                }
            }
        }
        return dp[mid];
    }
}

二维动态规划
不同路径

class Solution {
    /**
        dp[i][j] 表示从start点走到(i, j)的位置，总共有多少条不同路径
        dp[i][j]  dp[i - 1][j] 向右  dp[i][j - 1] 向下
     */
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for(int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

最小路径和

class Solution {
    /**
        dp[i][j]表示从左上角到(i, j)位置的最小数字总和
        dp[i][j] 只能由d[i - 1][j]向右，        或者d[i][j - 1]向下
                dp[i - 1][j] + nums[i][j]     dp[i][j - 1] + nums[i][j]   
     */
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for(int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for(int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]);
            }
        }
        return dp[m - 1][n - 1];
    }
}

最长回文子串

class Solution {
    /**
        dp[i] 以字符串的第i个位置的字母结尾的最长回文子串
        不太理解
        双指针法能写
        判断是否回文子串 奇数 i 向两边扩散, 偶数i i+1 向两边扩散
     */
    public String longestPalindrome(String