代码随想录 Day41 - 动态规划(三)

简介: 代码随想录 Day41 - 动态规划(三)

343. 整数拆分

DP 五部曲:

  1. 定义 dp 数组及下标含义:本题定义为拆分数字 i,得到的最大乘积为 dp[i];
  2. 确定递推公式: dp[i] = max(dp[i], (i - j) * j, dp[i- j] * j} );
  3. 初始化,dp[0]/dp[1]无意义,可以从 2 开始,dp[2] = 1;
  4. 确认遍历顺序;
  5. 举例推导 dp 数组(打印 dp 数组,验证是否符合预期);
package jjn.carl.dp;
import java.util.Scanner;
/**
 * @author Jjn
 * @since 2023/8/7 23:22
 */
public class LeetCode343 {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j < i - 1; j++) {
                dp[i] = Math.max(dp[i], Math.max((i - j) * j, dp[i - j] * j));
            }
        }
        return dp[n];
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int integerBreak = new LeetCode343().integerBreak(n);
        System.out.println(integerBreak);
    }
}


96. 不同的二叉搜索树

DP 五部曲:

  1. 定义 DP 数组含义:dp[i]可以表示为从 1~i 为不同元素节点组成的二叉搜索树的个数;
  2. 确认递推公式: dp[i] += dp[j - 1] * dp[i - j]
  3. 初始化 dp 数组,dp[0] = 1
  4. 确认遍历顺序,因为状态 i 依赖此前的状态,故从 1 开始遍历到 i
  5. 举例推导 dp 数组,辅助打印确认是否正确。
package jjn.carl.dp;
import java.util.Scanner;
/**
 * @author Jjn
 * @since 2023/8/7 23:53
 */
public class LeetCode96 {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int numTrees = new LeetCode96().numTrees(n);
        System.out.println(numTrees);
    }
}

目录
相关文章
|
存储 算法 测试技术
FPGA(现场可编程门阵列)技术概述及其应用实例
FPGA(现场可编程门阵列)技术概述及其应用实例
|
算法 数据挖掘 Python
【数据挖掘】层次聚类DIANA、AGNES算法讲解及实战应用(图文解释 超详细)
【数据挖掘】层次聚类DIANA、AGNES算法讲解及实战应用(图文解释 超详细)
1133 0
|
JavaScript Java 测试技术
基于SpringBoot+Vue的教学评价管理系统的详细设计和实现(源码+lw+部署文档+讲解等)
基于SpringBoot+Vue的教学评价管理系统的详细设计和实现(源码+lw+部署文档+讲解等)
144 2
|
12月前
|
数据采集 数据管理 数据挖掘
CDGP|数据治理策略揭秘:因企制宜,实现精准管控新高度
数据治理是指通过制定一系列政策、流程和技术手段,对企业数据进行全面、系统、规范的管理。它不仅能够确保数据的准确性、一致性和安全性,还能提升数据的质量和价值,为企业决策提供有力支持。因此,制定数据治理策略的首要任务是明确其核心价值,确保策略能够服务于企业的整体战略目标。
|
安全 PHP 数据安全/隐私保护
攻防世界17.fileinclude
攻防世界17.fileinclude
|
存储 缓存 监控
构建高效的Java缓存策略
【4月更文挑战第18天】本文探讨了如何构建高效的Java缓存策略,强调缓存可提升系统响应和吞吐量。关键因素包括缓存位置、粒度、失效与更新策略、并发管理、序列化及选择合适库(如Ehcache、Guava Cache、Caffeine)。最佳实践包括明确需求、选择合适解决方案、监控调整及避免常见陷阱。缓存优化是一个持续过程,需根据需求变化不断优化。
247 5
|
缓存 搜索推荐
【电脑知识】Edge浏览器的使用技巧(特别详细)
【电脑知识】Edge浏览器的使用技巧(特别详细)
601 0
|
JavaScript Windows 内存技术
windows下使用winget快速安装nvm
windows下使用winget快速安装nvm
316 0
|
安全 区块链 数据安全/隐私保护
带你读《自主管理身份:分布式数字身份和可验证凭证》——第2章 自主管理身份的基本组成部分
带你读《自主管理身份:分布式数字身份和可验证凭证》——第2章 自主管理身份的基本组成部分
带你读《自主管理身份:分布式数字身份和可验证凭证》——第2章 自主管理身份的基本组成部分
|
存储 程序员 编译器
【C语言】你不知道的隐式类型转换规则
本文接着C语言中的操作符(万字详解)讲解隐式类型转换规则,还有没学操作符的老铁可以回头看看。 在 C 语言中,类型转换的方式一般可分为隐式类型转换和显示类型转换(也称为强制类型转换)。 其中隐式类型转换由编译器自动进行,不需要程序员干预。 隐式类型转换通常有两种情况:整形提升和算术转换。
642 0