动态规划题目

   509 斐波那契数

class Solution {
    public int fib(int n) {
        /**
        dp[i]：第i个斐波那契数为dp[i]

        状态转移方程;
        dp[i] = dp[i - 1] + dp[i - 2]

        初始化：
        dp[0] = 0;
        dp[1] = 1;

        遍历顺序：
        由转移方程可知，从左到右
        */

        if(n <= 1){
            return n;
        }

        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;

        for(int i = 2; i < n + 1; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
}

70 爬楼梯

class Solution {
    public int climbStairs(int n) {
        if(n < 2){
            return n;
        }
        int[] ans = new int[n + 1];
        ans[1] = 1;
        ans[2] = 2;

        for(int i = 3; i <= n; i++){
            ans[i] = ans[i - 1] + ans[i - 2];
        }

        return ans[n];
    }
}

746 使用最小花费爬楼梯

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        /**
        dp[i]：爬到下标为i的阶梯的时候，花费的最小体力值为dp[i]

        状态转移方程：
        当到达一个阶梯的时候，可以有两个选项，一个是爬一格到达的这个阶梯，一个是爬两格到达的这个阶梯
        则dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

        初始化：
        由转移方程可知，必须初始化dp[0]
        dp[0] = 0
        dp[1] = cost[0];
        */

        int[] dp = new int[cost.length + 1];
        //dp[0]和dp[1]都是0，因为可以直接走到第一和第二个台阶
        dp[0] = 0;
        dp[1] = 0;
        dp[2] = Math.min(cost[0], cost[1]);

        if(cost.length == 2){
            return Math.min(cost[0], cost[1]);
        }

        for(int i = 3; i < cost.length + 1; i++){
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

        return dp[cost.length];
    }
}

62. 不同路径

class Solution {
    public int uniquePaths(int m, int n) {
        /**
        dp[i][j]：到达（i，j）时候，有dp[i][j]种路径

        状态转移方程:
        （要到达dp[i][j]，想想有哪些之前的情况可以组成dp[i][j]）
        要到达dp[i][j]，则有两种情况，一个是上一步往下走然后到达的dp[i][j]，则上一步为dp[i - 1][j]
        一个是上一步往右走，然后到达的dp[i][j]，则上一步为dp[i][j - 1]
        则dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

        初始化：
        由转移方程可知，必须初始化dp[0][j]和dp[i][0]，这两个的意义是：直走下边和直走右边
        直走则只有一条路径，则dp[0][j] = 1; dp[i][0] = 1

        遍历顺序：
        从左往右，从上到下
        */

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

63. 不同路径 II
 

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        /**
        dp[i][j]：当到达（i，j）的时候，路径的总数

        状态转移方程：
        同上
        当（i，j）为障碍物时，则直接跳过不予考虑

        初始化：
        往右往下只有一条路径，当碰到障碍物时，往右往下将不再有路径，全为0
        */

        

        int[][] dp = new int[obstacleGrid.length][obstacleGrid[0].length];
        for(int i = 0; i < obstacleGrid.length; i++){
            if(obstacleGrid[i][0] == 0){
                dp[i][0] = 1;
            }else{
                break;
            }
        }

        for(int j = 0; j < obstacleGrid[0].length; j++){
            if(obstacleGrid[0][j] == 0){
                dp[0][j] = 1;
            }else{
                break;
            }
        }

        for(int i = 1; i < obstacleGrid.length; i++){
            for(int j = 1; j < obstacleGrid[0].length; j++){
                if(obstacleGrid[i][j] == 0){
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }

        return dp[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
    }
}

96. 不同的二叉搜索树

class Solution {
    public int numTrees(int n) {
        /**
        思路：
        数组：dp[i]表示i个结点从1到i组成的二叉搜索树的个数
        递推公式：dp[i] = 以1为根节点的二叉搜索树的个数+
                         以2为根节点的二叉搜索树的个数+
                         以3为根节点的二叉搜索树的个数+
                         ...
                         以i-1为根节点的二叉搜索树的个数+
                         以i为根节点的二叉搜索树的个数
        对于dp[i]，以j为根节点的二叉搜索树的个数为:左子树的个数*右子树的个数
        dp[j - 1] * dp[i - j]
        初始化：dp[0] = 1;
               dp[1] = 1;
               
         */

        int[] dp = new int[n + 1];
        dp[0] = 1;//空结点也是一颗二叉树
        dp[1] = 1;

        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= i; j++){//当根节点为j时, 根节点只能从1开始
            //1, 2, 3, 4... j-1, j, j+1, j+2, j+3,... i;
            //前半部分个数为j-1, 后半部分个数为i-(j+1)+1=i-j;
                dp[i] += dp[j - 1] * dp[i - j];//进行笛卡尔积（每一个类型的左子树，都有很多右子树）
            }
        }

        return dp[n];
    }
}

343. 整数拆分

class Solution {
    public int integerBreak(int n) {
        /**
        思路：
        数组意义：dp[i]表示dp[i]拆分之后的最大成绩
        遍历：将i拆分成1 + i-1, 2 + i-2, ..., j + i-j
        在从1到j遍历的过程中，找出最大的那个分配方式
        每一次拆分相乘，又有两种方式，一个是只有两个，则为j*(i-j)
                                    一个是可以继续进行拆分，则为j*dp[i-j];
        在其中又找出最大的那一个
         */
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 0;
        dp[2] = 1;

        for(int i = 3; i <= n; i++){
            for(int j = 1; j <= i - 1; j++){
                /**
                选择dp[i]：表明当前的j不能用来拆分i
                选择j * (i - j)：表明选择了当前的j，并且分解成两个整数
                选择j * dp[i - j]：表明选择了当前j，并且分解成了j，以及其他的数
                */
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }

        return dp[n];
        
    }
}

416. 分割等和子集

class Solution {
    public boolean canPartition(int[] nums) {
        /**
        思路：如果两个子集相等，说明每一个子集都是sum / 2，所以sum必定是奇数。转化为01背包问题，
        sum / 2是背包的大小，元素的重量和价值都是nums[i]
         */

        int sum = 0;
        if(nums.length == 0 || nums.length == 1){
            return false;
        }

        for(int n : nums){
            sum += n;
        }

        if(sum % 2 == 1){
            return  false;
        }


        int target = sum / 2;
        int[] dp = new int[target + 1];//默认全部初始化为0
        for(int i = 0; i < nums.length; i++){
            for(int j = target; j >= nums[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }

        return dp[target] == target;//所取得元素的价值<=背包的最大容量，当等于时，符合条件
    }
}

1049. 最后一块石头的重量 II

class Solution {
    public int lastStoneWeightII(int[] stones) {
        /*
        思路：
        设定两堆石头，第一堆h1是用来粉碎第二堆h2的，那么只要找到这么一堆石头，使得
        当h1 - h2的时候，尽可能地接近于0，那么就能找到答案，也就是说要找到一堆h2，尽量要趋近于h1，
        最好就是h2 == h1.因此设定背包为h2 = sum / 2，在stones里面尽可能地找石头，让它的重量尽可能
        趋近于sum的一半
        */
        int sum = 0;
        for(int i : stones){
            sum += i;
        }

        int bagSize = sum / 2;

        int[] dp = new int[bagSize + 1];
        for(int i = 0; i < stones.length; i++){
            for(int j = bagSize; j >= stones[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }

        return (sum - dp[bagSize]) - dp[bagSize];

    }
}

494. 目标和

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        /**
        思路：将整个nums数组分成两大部分，分别是left和right，且
        left - right = target
        那么只要求出left有多少种，就知道能够组合成target的方式就有多少种
        设dp[i]为装满i的所有方法
        因为right = sum - left，带入得
        left = (target + sum) / 2；

         */

        int sum = 0;
        for(int i : nums){
            sum += i;
        }

        if((target + sum) % 2 != 0){//可以找一下反例，看看向下取整之后还符不符合条件
            return 0;
        }

        int bagSize = (target + sum) / 2;
        if(bagSize < 0){//左边部分设计的是大于等于零的，现在小于零了，则不成立
            return 0;
        }

        int[] dp = new int[bagSize + 1];
        dp[0] = 1;//初始化必须是非零的，否则依据递推公式，全部的都为零。填满空间为0的背包，有一        种方法，那就是什么也不放

        for(int i = 0; i < nums.length; i++){
            for(int j = bagSize; j >= nums[i]; j--){
                /**
                因为dp[j]表示加到j，有dp[j]种方法
                填满容量为j - nums[i]的背包，有dp[i - nums[i]]种方法

                到nums[0]时，填满j的方法和填满j - nums[0]的方法个数是一样的（所有的方法里面就                
加一
                个nums[0]而已）    
                到nums[1]时，填满j的方法和填满j - nums[0]的方法个数是一样的（所有的方法里面就加一
                个nums[1]而已）    
                ...

                那么，要填满j的背包，就是所有的填满j-nums[0],j-nums[1],j-nums[2]...所需要方法的
                总和

                 */
                dp[j] += dp[j - nums[i]];
            }
        }

        return dp[bagSize];

    }
}

474. 一和零

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        /**
        dp[i][j]：最多有i个0和j个1组成的字符串所组成的最大子串的大小
         */
        
        int[][] dp = new int[m + 1][n + 1];
        int oneNum, zeroNum;

        for(String str : strs){//这个循环，是遍历物品，这个物品，有两个维度
            oneNum = 0;
            zeroNum = 0;
            
            for(char ch : str.toCharArray()){
                if(ch == '0'){
                    zeroNum++;
                }else{
                    oneNum++;
                }
            }
            
            for(int i = m; i >= zeroNum; i--){
                for(int j = n; j >= oneNum; j--){
                    /**
                    dp[i - zeroNum][j - oneNum]为不加入当前字符串时的最大数量，
                    当最多为(i-zeroNum)+zeroNum, (j-oneNum)+oneNum时，当前字符串可以算进去了
                    则+1
                    dp[i - zeroNum][j - oneNum]是还没算入当前字符的个数
                     */
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
}

注意是种类问题，还是普通的价值问题

顺序不同构成的排序和组合，属于是完全背包问题

518. 零钱兑换 II

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        /**
        dp[i] += dp[i - coins[j]]
         */ 

        dp[0] = 1;
        for(int i = 0; i < coins.length; i++){   
            /**
            如果是先背包，后物品，则成了排列问题，如
            当背包为5时，构成的物品可以是1+4，而经过1时加了一次，经过4时又加了一次，如果是组合问题  
            则只能加1次，而这里加了2次 
             */
            for(int j = 1; j <= amount; j++){
                if(j >= coins[i]){
                    dp[j] += dp[j - coins[i]];
                }
            }
        }

        return dp[amount];
    }
}

377. 组合总和 Ⅳ

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;//dp[0] = 1是没有意义的，仅仅为了去推导公式
        
        for(int i = 1; i <= target; i++){
            for(int j = 0; j < nums.length; j++){
                if(i >= nums[j]){
                    dp[i] += dp[i - nums[j]];
                }
            }
        }

        return dp[target];
    }
}

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 j = 0; j < coins.length; j++){
                if(i >= coins[j]){
                    /**
                    先背包，后物品，但与排序组合问题无关

                    假如已经到了amount容量，那么dp[i]就要找所有
                    dp[i - coins[0]],dp[i - coins[1]],dp[i - coins[2]]...中，最小的那个数
                    然后 +1，得到dp[i]的值(寻找不包括某个coins[i]中，最小的那个，找到之后，加
                    入的就是这个coins[i])

                    Math.min目的不是让dp[j - coins[i]] + 1与dp[j]进行比较，而是在dp[0]到
                    dp[j - 1]中找到最小的那一个
                    */
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }

        if(dp[amount] > amount){//如果出现这种情况，说明就算原来的coins全为1，也不能符合条件了，说明没有能组成这个amount的组合
            return -1;
        }

        return dp[amount];
    }
}

279. 完全平方数

class Solution {
    public int numSquares(int n) {
        /**
         先得出weight:1~100
         dp[i]：形成i的最少完全平方数
         递推方程：dp[i] = Math.min(dp[i], dp[i - weight[j]] + 1)
         初始化：dp[1] = 1, dp[0] = 0,其余的为max = Integer.MAX_VALUE
         */
        int[] weight = new int[100];
        for(int i = 1; i <= 100; i++){
            weight[i - 1] = i*i;
        }

        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        dp[1] = 1;

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

139. 单词拆分

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        /*
        dp[i]：表示s的前i个字符中，如果可以表示为一个或多个在wordDict中出现的字符串，则为true
        递推公式：if(dp[j] == true && 在s[j + 1, i]中有在wordDict中的单词)，则dp[i] = true

        在一个i中，j从0到i-1，不断地将i进行切分，如果符合
        dp[j] = true && wordDict.contains(s.substring(i, j))，那么就符合要求了，那么dp[i]
        就可以设定为true了

        初始化dp[0] = 0。
        */

        boolean[] dp = new boolean[s.length() + 1];
        Arrays.fill(dp, false);
        dp[0] = true;//该初始化没有实际意义，但如果不设定为true，后面的全部都为false了，这是为了推导而设定的初始化的值

        for(int i = 1; i <= s.length(); i++){
            for(int j = 0; j < i; j++){
                if(dp[j] == true && wordDict.contains(s.substring(j, i))){
                    //substirng(i, j)，得到的子串为S[j, i - 1]
    
                    //如果初始化dp[0]不是true，那么没有一个元素能够进来
                    dp[i] = true;
                }
            }
        }

        return dp[s.length()];
    }
}

198. 打家劫舍

class Solution {
    public int rob(int[] nums) {
        /*
        dp[i]：偷到第i家的时候，得到的最多现金

        动态转移方程：
        （注意dp[i]本身就是一个叠加的过程，是一个可以迭代推进的过程，你要思考，当我到达这里的时候，
          与前面的有什么练习，怎么利用前面的内容来得到我现在要求的内容）
          
        当到达第i家的时候，可以选择偷或者不偷
            1)偷，则表明前一家不能偷，要从前前一家偷的金额再加上今天偷的这一家的金额，则为
              dp[i] = dp[i - 2] + nums[i]
            2)不偷，则表明到这一家的时候累计的金额等同于到上一家的时候累计的金额，则为
              dp[i] = dp[i - 1]
        取最大者

        初始化：
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1])（当只有两家的时候，选择偷大的那一家）

        遍历顺序：
        从左往右
        */
        if(nums.length == 1){
            return nums[0];
        }

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for(int i = 2; i < nums.length; i++){
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }

        return dp[nums.length - 1];
    }
}

213. 打家劫舍 II

class Solution {
    public int rob(int[] nums) {
        /*
        dp[i]：当偷到第i家的时候，所偷的总的钱数

        动态转移方程：
        因为时一个环，最开始和最末尾一家不同同时偷，考虑将这一个环分成两个部分来计算，一个部分是包含
        第一家而不包含最后一家，一部分是包含最后一家而不包含第一家，将得出的两个结果进行比较，输出大
        的那个，其他的与打家劫舍Ⅰ相同

        初始化：与打家劫舍Ⅰ相同
        */

        if(nums.length == 1){
            return nums[0];
        }

        if(nums.length == 2){
            return Math.max(nums[0], nums[1]);
        }

        int max = 0;
        int[] dp = new int[nums.length - 1];
        //考虑第一部分
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for(int i = 2; i < nums.length - 1; i++){
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }

        max = dp[dp.length - 1];

        //考虑第二部分
        dp[0] = nums[1];
        dp[1] = Math.max(nums[1], nums[2]);
        for(int i = 2; i < nums.length - 1; i++){
            dp[i] = Math.max(dp[i - 2] + nums[i + 1], dp[i - 1]);
        }

        return Math.max(dp[dp.length - 1], max);

    }
}

121. 买卖股票的最佳时机

class Solution {
    public int maxProfit(int[] prices) {
        /*
        dp[i][0,1]：到下标为i的时候，dp[i][0]表示不持有股票的时候，手里的现金，dp[i][1]表示持有股
        票的时候，手里持有的现金

        动态转移方程：
        计算dp[i][0]，不持有股票，有两种情况：
            1)昨天就不持有股票，则dp[i][0] = dp[i - 1][0]
            2)昨天持有的股票今天卖掉了，则dp[i][0] = dp[i - 1][1] + prices[i];

        计算dp[i][1]，持有股票，有两种情况:
            1)昨天就一直持有股票，则dp[i][1] = dp[i - 1][1]
            2)昨天没有持有股票，但今天买入了股票，则dp[i - 1][1] = - prices[i]（只买入一次）
        取最大的那个

        初始化：
        对于dp[0][0]，在第0天不持有股票，则现金为0
        对于dp[0][1]，在第0天就买了股票了，则现金为dp[0][1] = -prices[0]

        遍历顺序:
        从左往右
        */

        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0]; 
        for(int i = 1; i < prices.length; 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], -prices[i]);
        }

        return Math.max(dp[prices.length - 1][0], dp[prices.length - 1][1]);

    }
}

股票问题就是设定手里是否存有股票的状态

122. 买卖股票的最佳时机 II        714. 买卖股票的最佳时机含手续费

class Solution {
    public int maxProfit(int[] prices) {
        /*
        dp[i][0,1]：到下标为i的时候，dp[i][0]表示不持有股票的时候，手里的现金，dp[i][1]表示持有股
        票的时候，手里持有的现金

        动态转移方程：
        计算dp[i][0]，不持有股票，有两种情况：
            1)昨天就不持有股票，则dp[i][0] = dp[i - 1][0]
            2)昨天持有的股票今天卖掉了，则dp[i][0] = dp[i - 1][1] + prices[i];

        计算dp[i][1]，持有股票，有两种情况:
            1)昨天就一直持有股票，则dp[i][1] = dp[i - 1][1]
            2)昨天没有持有股票，但今天买入了股票，则dp[i - 1][1] = dp[i - 1][1] - prices[i]（买
              入卖出多次，所以需要用到前面已保存的状态）
        取最大的那个

        初始化：
        对于dp[0][0]，在第0天不持有股票，则现金为0
        对于dp[0][1]，在第0天就买了股票了，则现金为dp[0][1] = -prices[0]

        遍历顺序:
        从左往右
        */

        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0]; 
        for(int i = 1; i < prices.length; 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 Math.max(dp[prices.length - 1][0], dp[prices.length - 1][1]);

    }
}

123. 买卖股票的最佳时机 III

class Solution {
    public int maxProfit(int[] prices) {
        /*
        dp[i][1，2，3，4]：
        dp[i][0]：第一次交易时，没有股票时候手里的现金
        dp[i][1]：第一次交易时，有股票时候手里的现金
        dp[i][3]：第二次交易时，没有股票时候手里的现金
        dp[i][4]：第二次交易时，有股票时候手里的现金

        状态转移方程:
        第一次交易
        dp[i][0]，有两种情况：
            1)前一天就没有股票，则为dp[i - 1][0]
            2)前一天有股票，但是今天卖掉了，则为dp[i - 1][1] + prices[i]

        dp[i][1]，
            1)前一天就有股票，则为dp[i - 1][1]
            2)前一天没有股票，但是今天买入了（第一次持有），则为 -prices[i]

        第二次交易
        dp[i][2],
            1)前一天就没有股票，则为dp[i - 1][2]
            2)前一天有股票（此时的股票是第二次买入的股票），但是今天卖掉了，则为dp[i - 1][3] + prices[i] 

        dp[i][3],
            1)前一天就有股票，则为dp[i - 1][3]
            2)前一天没有股票，但是今天买入了，则买入的是第二次买入的股票，则需要在prices[i][0]的
              基础上减去买股票的钱，因为此时的prices[i][0]是第一次卖出之后，得到的最大利润，第二
              次操作应该从这个基础上开始

        初始化：
        dp[0][0]：第0天不持有，则为0
        dp[0][1]：第0天持有，则为-prices[0]
        dp[0][2]：第0天不持有，相当于当天买入，当天卖出，则为0
        dp[0][3]：第0天持有，相当于当天买入当天卖出，然后再买入，则为-prices[0]

        遍历顺序：
        从左到右
        */

        int[][] dp = new int[prices.length][4];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;
        dp[0][3] = -prices[0];

        for(int i = 1; i < prices.length; 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], -prices[i]);            
            

            //第二次，不持有股票
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][3] + prices[i]);
            //第二次，持有股票
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][0] - prices[i]);
        }  

        return dp[prices.length - 1][2];
    }
}

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

class Solution {
    public int maxProfit(int k, int[] prices) {
        /*
        dp[i][0,1,2,3,4,...,k*2 - 1]：
        第一次
        dp[i][0]：第一次交易，手里不持有股票时候的现金
            1)前一天就没有股票，为dp[i - 1][0]
            2)之前买入了第一次交易的股票，今天卖了，为dp[i - 1][1] + prices[i]
        dp[i][1]：第一次交易，手里持有股票时候的现金
            1)前一天就一直保留着第一支股票，为dp[i - 1][1]
            2)之前没有买股票，今天买入第一次交易的股票，为-prices[i]

        第二次：
        dp[i][2]：第二次交易，手里不持有股票时候的现金
            1)前一天就没有股票，为dp[i - 1][2]
            2)之前买入了第二次交易的股票，今天卖了，为dp[i - 1][3] + prices[i]
        dp[i][3]：第二次交易，手里持有股票时候的现金
            1)前一天就一直保留着第二支股票，为dp[i - 1][1]
            2)在上一次交易以后，今天买入这一次交易的股票，为dp[i - 1][0] - prices[i];
        
        第三次
        dp[i][4]：第三次交易，手里不持有股票时候的现金
            1)前一天就没有股票，为dp[i - 1][4]
            2)之前买入了第三次交易的股票，今天卖了，为dp[i - 1][5] + prices[i]
        dp[i][5]：第三次交易，手里持有股票时候的现金
            1)前一天就一直保留着第三支股票，为dp[i - 1][5]
            2)在上一次交易以后，今天买入这一次交易的股票，为dp[i - 1][2] - prices[i];

        第k次
        dp[i][k*2 - 2]：第k次交易，手里不持有股票时候的现金
            1)前一天就没有股票，为dp[i - 1][k*2 - 2]
            2)之前买入了第k次交易的股票，今天卖了，为dp[i - 1][k*2 - 1] + prices[i]
        dp[i][k*2 - 1]：第k次交易，手里持有股票时候的现金
            1)前一天就一直保留着第k支股票，为dp[i - 1][k*2 - 1]
            2)在上一次交易以后，今天买入这一次交易的股票，为dp[i - 1][k*2 - 1 - 3] - prices[i];


        初始化：
        在第0天，每一次的持有，都是-prices[0]，每一次的不持有，都是0，则由上面可知，偶数为不持有，
        奇数为持有

        遍历顺序，从上到下，从左到右

        */

        if(prices.length <= 1 || k == 0){
            return 0;
        }

        int[][] dp = new int[prices.length][k*2];
        for(int i = 0; i < k*2; i++){
            if(i % 2 == 0){
                dp[0][i] = 0;
            }else{
                dp[0][i] = -prices[0];
            }
        }

        for(int i = 1; i < prices.length; 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], -prices[i]);

            for(int j = 2; j < k*2; j++){

                /* 
                如果是0，2，4，k*2 - 2这种偶数，则属于是不持有
                如果是1，3，5，k*2 - 1这种奇数，则属于是持有
                */

                if(j % 2 == 0){
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j + 1] + prices[i]);
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 3] - prices[i]);
                }

            }
        }

        return dp[prices.length - 1][k*2 - 2];
    }
}

309. 最佳买卖股票时机含冷冻期

class Solution {
    public int maxProfit(int[] prices) {
        /**
        dp[i][3]:

        dp[i][0]：在第i天时，有股票时手里的现金
        不持有分两种，一种是今天卖了的不持有，一种是今天没有卖的不持有
        dp[i][1]：在第i天时，手里没有股票，但是明天将处于冷冻期中（也就是说在这一天是卖出了股票了的）
        dp[i][2]：在第i天时，手里没有股票，而且明天也不处于冷冻期中（也就是说至少今天没有卖股票）

        动态转移方程：
        dp[i][0]:
            1)本来手里就一直拿着这只股票，则为dp[i - 1][0]
            2)之前没有股票，今天买入了股票（要不处于冷冻期中才可以，所以用dp[i - 1][2]）,则为
              dp[i - 1][2] - prices[i];
        
        dp[i][1]：
            1)今天卖出了股票，则为dp[i - 1][0] + prices[i]

        dp[i][2]：
            1)本来就一直没有股票，则为dp[i - 1][1]
            2)昨天把股票买了，今天为冷冻期，则为dp[i - 1][2]

        初始化：
        在买入的时候为-prices[0]

        遍历顺序：
        从左到右
        */

        int[][] dp = new int[prices.length][3];
        dp[0][0] = -prices[0];
        for(int i = 1; i < prices.length; i++){
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i]);
            dp[i][1] = dp[i - 1][0] + prices[i];
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1]);
        }

        return Math.max(dp[prices.length - 1][1], dp[prices.length - 1][2]);
    }
}

注意买卖次数有限制和无限制的区别

300. 最长递增子序列

class Solution {
    public int lengthOfLIS(int[] nums) {
        /**
        dp[i]：表示从下标0开始，到以nums[i]为结尾的子序列的最大长度

        动态转一方程:
        若nums[i]>nums[j]，则dp[i] = [0, i-1]中最大的那个最长子序列的长度 + 1
        
        初始化：
        因为长度至少为1，所以整个数组初始化为1


        遍历顺序:
        由图可知是从左往右推出
        
        */
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);

        int max = 1;
        for(int i = 0; i < nums.length; i++){
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);//(选取在[0, i-1]中，结尾小于nums[i]的子序列的最大长度)，并不是说要将dp[i]与dp[j] + 1进行比较
                    max = Math.max(dp[i], max);
                }
            }
        }

        return max;
    }
}

674. 最长连续递增序列

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        /**
        dp[i]：到达i下标时，找到的连续递增子序列的最长长度

        状态转移方程：
        如果nums[i - 1] < nums[i]那么，dp[i] = dp[i - 1] + 1;
        否则的话，从1重新开始记录，同时记录下最大的那个值

        初始化：
        最小都为1

        遍历次序：
        由图可知，是从左往右递推的
        */

        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);

        int max = 1;
        for(int i = 1; i < nums.length; i++){
            if(nums[i - 1] < nums[i]){
                dp[i] = dp[i - 1] + 1;
            }
            max = Math.max(max, dp[i]);
        }

        return max;
    }
}

求数组，则若不符合条件了，从当前情况重新开始；求子序列，若不符合条件了，则继承前面的情况继续下去

718. 最长重复子数组
 

class Solution {
    public int findLength(int[] A, int[] B) {
        /**
        dp[i][j]：表示当到达A的i-1下标和B的j-1下标地时候，所得到的最长子数组的长度

        转移方程：
        只有当nums1[i] == nums2[j]的时候，才能在之前的基础dp[i - 1][j - 1]上面加1
        一旦nums1[1] != nums2[j]了，那么就得重新开始了，因为要找的是数组（连续子序列）
        
        初始化
        因为一开始不可能有相同的，也不知道哪个是相同的，所以全部设置为0        

        遍历顺序：
        由图可知，是从左上到右下，从上到下，从左到右
        */

        int res = 0;
        int[][] dp = new int[A.length + 1][B.length + 1];
        for(int i = 1; i < A.length + 1; i++){
            for(int j = 1; j < B.length + 1; j++){
                if(A[i - 1] == B[j - 1]){
                    /*
                    只有当A[i - 1] == B[i - 1]时，才在前面这个基础上的最大长度再加1
                    前面基础上的最大长度也就是dp[i - 1][j - 1]，
                    即在到达A[i - 2], B[j - 2]时，dp中所保存的最大长度
                    */
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    res = Math.max(res, dp[i][j]);
                }
            }
        }

        return res;
    }
}

1143. 最长公共子序列         1035. 不相交的线        392. 判断子序列        583. 两个字符串的删除操作

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        /**
        dp[i][j]：到nums1的i-1和nums2的j-1的时候，最长公共子序列为dp[i][j]

        状态转移方程：
        当nums1[i] == nums2[j]的时候，dp[i][j]为在前面的基础上+1
        当nums1[i] != nums2[j]的时候，dp[i][j]取dp[i - 1][j]和dp[i][j - 1]中最大的哪个。因为                
        求的是子序列，所以结果可以延续下来

        初始化：
        因为对nums1和nums2的情况都未知，所以全部设为0

        遍历顺序：
        由转移方程可知是从左上到右下，从上到下，从左到右
        */

        char[] A = text1.toCharArray();
        char[] B = text2.toCharArray();

        int[][] dp = new int[A.length + 1][B.length + 1];

        for(int i = 1; i < A.length + 1; i++){
            for(int j = 1; j < B.length + 1; j++){
                if(A[i - 1] == B[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                /**
        ​          如果不相等，那么在包含i或j的情况下，A或B再往前退一步，看看
        ​          A[0:i - 1]和B[0,j]或A[0,i]和B[0,j-1]中，那个有最大长度的子序列
​                */
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[A.length][B.length];
    }
}

53. 最大子序和

class Solution {
    public int maxSubArray(int[] nums) {
        /**
        dp[i]：当到达nums的i下标时，得到的最大和为dp[i]

        状态转移方程：
        加入一个数，若加入后的数大于当前的数，则选加入后的（增加一个成员），若当前的数大于加入后的数，那么选择当前的数（在当前重新开始，以当前为最初状态）
        dp[i] = Math.max(dp[i], nums[i])

        初始化：
        从0开始,若是最坏情况，全部都是负的，那么只选择第一个元素nums[0]
        dp[0] = nums[0]

        遍历顺序：从左往右
        */
        int[] dp = new int[nums.length];
        dp[0] = nums[0];

        int res = nums[0];
        for(int i = 1; i < nums.length; i++){
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
            res = Math.max(res, dp[i]);
        }

        return res;
    }
}

115. 不同的子序列

class Solution {
    public int numDistinct(String s, String t) {
        /**
        dp[i][j]：到达s[i-1]和t[j-1]的时候，s中包含t的个数为dp[i][j]

        状态转移方程：
        当S[i - 1] == T[j - 1]时，此时，dp[i][j]由两部分构成：
            1)第一部分：包含S[i - 1]进行匹配，那么相同的S[i - 1]和T[j - 1]就不用看了，直接数
              前面的那些，则dp[i][j] = dp[i - 1][j - 1]
            2)第二部分：不包含S[i - 1]进行匹配，则dp[i][j] = dp[i - 1][j]

        当S[i - 1] != T[j - 1]时，就相当于上面的第二部分，dp[i][j] = dp[i - 1][j]

        初始化：
        当i = 0，即s为空时，不可能有任何的匹配
        当j = 0，即t为空时，空字符串是任何字符串的子串，所以对于所有的i，都有dp[i][j] = 1;

        遍历顺序：
        由状态转移方程可知，是从上往下推和从左上往右下推
        */

        char[] S = s.toCharArray();
        char[] T = t.toCharArray();

        int[][] dp = new int[S.length + 1][T.length + 1];
        for(int i = 0; i < S.length + 1; i++){
            dp[i][0] = 1;
        }

        for(int i = 1; i < S.length + 1; i++){
            for(int j = 1; j < T.length + 1; j++){
                if(S[i - 1] == T[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
                
            }
        }

        return dp[S.length][T.length];
    }
}

若同时出现两个数组，一般情况下都是要分当c1[i]与c2[j]是否相等的情况。而且当初始化的时候，要注意当其中一个字符串为空时候的情况

583. 两个字符串的删除操作

class Solution {
    public int minDistance(String word1, String word2) {
        /**
        dp[i][j]：当到达word1[i - 1]和word[j - 1]的时候，为了使两者相同所需要删除的最少步数

        动态转移方程：
        当word1[i - 1] == word2[j - 1]时，不进行操作，dp[i][j] = dp[i - 1][j - 1]
        当word1[i - 1] != word2[j - 1]时，要进行删除操作，有下面三种情况：
            1)删除word1[i - 1]，则dp[i][j] = dp[i - 1][j] + 1
            2)删除word2[j - 1]，则dp[i][j] = dp[i][j - 1] + 1
            3)两个都删除，则dp[i][j] = dp[i - 1][j - 1] + 2;
            取其中最小的那个

        初始化：
        当word1为空字符时，若要两者相等，则word2得删完所有字符，反之亦然

        遍历顺序：
        从上往下，从左往右
        */
        char[] c1 = word1.toCharArray();
        char[] c2 = word2.toCharArray();
        int[][] dp = new int[c1.length + 1][c2.length + 1];

        for(int i = 0; i < c1.length + 1; i++){
            dp[i][0] = i;
        }

        for(int j = 0; j < c2.length + 1; j++){
            dp[0][j] = j;
        }


        for(int i = 1; i < c1.length + 1; i++){
            for(int j = 1; j < c2.length + 1; j++){
                if(c1[i - 1] == c2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + 2, Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                }
            }
        }

        return dp[c1.length][c2.length];
    }
}

72. 编辑距离

class Solution {
    public int minDistance(String word1, String word2) {
        /**
        dp[i][j]：到达word1[i - 1]和word2[j - 1]的时候，将word1转化为word2所需要的最少操作数为
        dp[i][j]

        状态转移方程：
        当c1[i - 1] == c2[j - 1]时，不需要进行处理dp[i][j] = dp[i - 1][j - 1]
        当c1[i - 1] != c2[j - 1]时，有以下三种情况处理：
            1)删除c1[i - 1]，则dp[i][j] = dp[i - 1][j] + 1
            2)在c1[i - 1]后面增加元素，也就相当于删除c2[j - 1]，两者的操作是等价的，则
              dp[i][j] = dp[i][j - 1];
            3)替换掉c1[i - 1]，若替换掉，则c1[i - 1] == c2[j - 1]，所以根据到
              c1[i - 2],c2[j - 2]的时候为基础计算（取计算到c1[i - 2],c2[j - 2]的时候编辑的次数），则dp[i][j] = dp[i - 1][j - 1] + 1
            然后取最小的那个

        初始化：
        当word1为空字符串时，若要变成word2，则要增加word2的全部元素
        当word2为空字符串时，若word1要变成word2，则要减去word1的全部元素

        遍历顺序：
        从上往下从左往右
        */


        char[] A = word1.toCharArray();
        char[] B = word2.toCharArray();

        int[][] dp = new int[A.length + 1][B.length + 1];

        for(int i = 1; i < A.length + 1; i++){
            dp[i][0] = i;
        }

        for(int j = 1; j < B.length + 1; j++){
            dp[0][j] = j;
        }

        for(int i = 1; i < A.length + 1; i++){
            for(int j = 1; j < B.length + 1; j++){
                if(A[i - 1] == B[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    /*
                    操作一：word1删除一个元素，那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。
即 dp[i][j] = dp[i - 1][j] + 1;
                    操作二：word2删除一个元素，那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。
即 dp[i][j] = dp[i][j - 1] + 1;
                    操作三：替换元素，word1替换word1[i - 1]，使其与word2[j - 1]相同，此时不用增加元素，那么以下标i-2为结尾的word1 与 j-2为结尾的word2的最近编辑距离 加上一个替换元素的操作。
即 dp[i][j] = dp[i - 1][j - 1] + 1;
                     */
                    dp[i][j] = Math.min(dp[i - 1][j] + 1, Math.min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1));
                }                
            }
        }

        return dp[A.length][B.length];

    }
}

647. 回文子串
 

class Solution {
    public int countSubstrings(String s) {
        /**
        dp[i][j]：在[i, j]的位置时，若是回文字符串，则为true

        动态回归方程：
        当S[i] != S[j]时，一定不是回文字符串

        当S[i] == S[j]时
            1)若i=j，则必定为回文字符串
            2)若j-i = 1，则必为回文字符串（“aa”）
            3)若j-i > 1，则判断[i + 1, j - 1]是不是回文字符串，若是，则[i, j]必定是回文字符串
              如（“avcva”）
              
        初始化：
        全为false，或设置dp[i][j] = true，其中i=j

        遍历顺序：
        由图可知，dp[i][j]由左下角推出来，所以遍历顺序是从上往下，从左往右
        */
        
        char[] S = s.toCharArray();
        boolean[][] dp = new boolean[S.length][S.length];
        int result = 0;
        for(int i = S.length - 1; i >= 0; i--){
            for(int j = i; j < S.length; j++){
                if(S[i] == S[j]){
                    if(i == j){
                        result++;
                        dp[i][j] = true;
                    }

                    if(j - i == 1){
                        result++;
                        dp[i][j] = true;
                    }

                    if(j - i > 1 && dp[i + 1][j - 1] == true){
                        result++;
                        dp[i][j] = true;
                    }
                }
            }
        }

        return result;
        
    }
}

516. 最长回文子序列

class Solution {
    public int longestPalindromeSubseq(String s) {
        /*
        dp[i][j]：在[i, j]中子串的最长回文子序列长度

        转移方程：
        当s[i] == s[j]时，那么在里面一层最长子序列长度的基础上+2
        当s[i] != s[j]时，有两种情况
            1.取[i+1, j]中最长子序列长度
            2.取[i, j-1]中最长子序列长度

        初始化：最开始的dp为dp[0][0]（从dp[i][j - 1]得出），且所有i=j时，dp[i][j] = 1

        遍历次序：
        有图可知，有三个方向：
            1.从左下推出右上
            2.从下推出上
            3.从左推出右
        则遍历次序为，从下到上，从左往右
        */

        char[] S = s.toCharArray();
        int[][] dp = new int[S.length][S.length];
        for(int i = 0; i < S.length; i++){
            for(int j = 0; j < S.length; j++){
                if(i == j){
                    dp[i][j] = 1;
                }
            }
        }

        int result = 1;
        for(int i = S.length - 1; i >= 0; i--){
            for(int j = i + 1; j < S.length; j++){
                if(S[i] == S[j]){
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                }else{
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }

                result = Math.max(result, dp[i][j]);
            }
        }

        return result;
    }
}

待后续补充

最后

以上就是迷你航空为你收集整理的动态规划题目的全部内容，希望文章能够帮你解决动态规划题目所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。