代码随想录算法训练营第四十五天 _ 动态规划_ 70. 爬楼梯、322.零钱兑换、279.完全平方数、139.单词拆分。

2023-12-13 06:39:25

学习目标:

动态规划五部曲:
① 确定dp[i]的含义
② 求递推公式
③ dp数组如何初始化
④ 确定遍历顺序
⑤ 打印递归数组 ---- 调试
引用自代码随想录!

60天训练营打卡计划!

学习内容:

70. 爬楼梯

  • 动态规划五步曲:
    ① 确定dp[j]的含义 : 容量为j的背包可以放dp[j]种排列
    ② 求递推公式 : dp[j] += dp[j-i]; (排列问题的标准递推公式!)
    ③ dp数组如何初始化 : dp[0] = 1
    ④ 确定遍历顺序 : 排列问题!先遍历背包,再遍历物品!
class Solution {
    // 使用完全背包再做!
    // 是一种排列问题!
    // 先遍历背包,再遍历物品!
    public int climbStairs(int n) {
        // dp数组的含义是:容量为j的背包可以放dp[j]种排列
        int[] dp = new int[n + 1];

        // 初始化
        dp[0] = 1;
        
        // 递归逻辑
        for(int j = 1; j <= n; j++){
            for(int i = 1; i <= 2 && j >= i; i++){
                dp[j] += dp[j-i];
            }
        }

        return dp[n];
    }
}

322.零钱兑换

  • 动态规划五步曲:
    ① 确定dp[j]的含义 : 装满容量为i的背包,最少的物品数量dp[j]
    ② 求递推公式 : dp[j] = min(dp[j-coins[i]]+1, dp[j])
    ③ dp数组如何初始化 : dp[0] = 0 其他的都是Integer.MAX_VALUE
    ④ 确定遍历顺序 : 都可以,因为不管是排列还是组合,元素的个数是一样的。

  • 因为初始值是Integer.MAX_VALUE,再做加法就会溢出,一定会成为最小值。所以在递归的最小逻辑上要额外的判断,如果(dp[j - coins[i]]是最大值,说明该位没有意义,没有被选择的意义。

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        int itemSize = coins.length;

        // 初始化
        dp[0] = 0;
        for(int i = 1; i <= amount; i++){
            dp[i] = Integer.MAX_VALUE;
            // System.out.println(dp[i] + " ");
        }
        // System.out.println("*");

        // 递归逻辑
        for(int i = 0; i < itemSize; i++){
            for(int j = coins[i]; j <= amount; j++){
                //只有dp[j-coins[i]]不是初始最大值时,该位才有选择的必要
                if (dp[j - coins[i]] != Integer.MAX_VALUE) {
                    //选择硬币数目最小的情况
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
                // System.out.println(dp[j] + " ");
            }
            // System.out.println("*");
        }

        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

279.完全平方数

  • 动态规划五步曲:
    ① 确定dp[j]的含义 : 凑成 i 这个数需要的最少的完全平方数的个数dp[j]。
    ② 求递推公式 : dp[j] = min(dp[j] , dp[j-i*i]+1)
    ③ dp数组如何初始化 : dp[0] = 0 其他的都是Integer.MAX_VALUE
    ④ 确定遍历顺序 : 都可以,因为不管是排列还是组合,元素的个数是一样的。

  • 本题的特殊之处在于物品遍历时的结束条件:i*i <= n ,太精髓了!

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];

        // 初始化
        for(int j =0; j <= n; j++){
            dp[j] = Integer.MAX_VALUE;
        }
        dp[0] = 0;

        // 递归逻辑,需要考虑终止的条件i*i <= n
        // 如果取i < n/2的话,1和2无法进入循环
        for(int i = 1; i*i <= n; i++){
            for(int j = i*i; j <= n; j++){
                if(dp[j - i*i] != Integer.MAX_VALUE){
                    dp[j] = Math.min(dp[j], dp[j - i*i]+1);
                }
            }
        }
        return dp[n];
    }
 }

139.单词拆分

  • 动态规划五步曲:
    ① 确定dp[i]的含义 : 当前 i 长度的字符串可以被字典中共计dp[i]个单词组成。
    ② 求递推公式 :
// 只有当dp[j]可以被wordDict组成的时候,才有必要去继续比较
                if(dp[j] != -1 && set.contains(sub)){
                    dp[i] = dp[j] + 1;
                }

③ dp数组如何初始化 : dp[0] = 0 dp[其他] = -1
④ 确定遍历顺序 :先遍历背包,再遍历物品,因为本题是一种排列。
背包指的肯定是字符串s,背包里装的是截至i长度的字符串可以被字典中的几个单词组成;物品指的是字典中的单词。

// 使用上述的动态规划思想完成的代码,可以更好地被视为完全背包问题。
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>();
        for(int i = 0; i < wordDict.size(); i++){
            set.add(wordDict.get(i));
        }
        // 指的是截至i长度的字符串被几个单词组成
        int[] dp = new int[s.length() + 1];

        // 初始化
        dp[0] = 0;
        for(int i = 1; i <= s.length(); i++){
            dp[i] = -1;
        }

        // 递推逻辑  - 算是一种排列,所以先背包后物品
        for(int i = 0; i <= s.length(); i++){
            for(int j = 0; j < i; j++){
                // 左闭右开
                String sub = s.substring(j, i);
                // 只有当dp[j]可以被wordDict组成的时候,才有必要去继续比较
                if(dp[j] != -1 && set.contains(sub)){
                    dp[i] = dp[j] + 1;
                }
            }
        }
        // for(int i : dp){
        //     System.out.println(i + " ");
        // }
        return dp[s.length()] != -1 ? true : false;
    }
}
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>();
        for(int i = 0; i < wordDict.size(); i++){
            set.add(wordDict.get(i));
        }
        boolean[] dp = new boolean[s.length() + 1];

        // 初始化
        dp[0] = true;
        for(int i = 1; i < s.length(); i++){
            dp[i] = false;
        }

        // 递推逻辑  - 算是一种排列,所以先背包后物品
        for(int i = 0; i <= s.length(); i++){
            for(int j = 0; j < i; j++){
                // 左闭右开
                String sub = s.substring(j, i);
                // 只有当dp[j]为true的时候,才有必要去继续比较
                // 代表前一段可以被wordDict组成
                if(dp[j] == true && set.contains(sub)){
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }
}

学习时间:

  • 上午两个半小时,整理文档半小时。

文章来源:https://blog.csdn.net/weixin_46367158/article/details/134847267
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。