算法刷题记录 Day35

算法刷题记录 Day35

Date: 2024.04.01

lc 96. 不同的二叉搜索树

class Solution {
public:
    int numTrees(int n) {
        if(n <= 2)
            return n;
            
        // 二叉搜索树:左结点小于根结点,右结点大于根结点;
        vector<int> dp(n+1, 0);
        // dp[i]表示由i个结点的二叉搜索树有多少种;
        // dp[i] = for(int t=1; t<=i; t++){ dp[i] += dp[t-1] * dp[i-t]}    t为根结点的值
        // dp[0] = 0; dp[1] = 1; dp[2] = 2;
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3; i<=n; i++){
            for(int t=1; t<=i; t++){
                dp[i] += (dp[t-1] * dp[i-t]);
            }
        }
        return dp[n];
    }
};

lc 343. 整数拆分

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1, 0);
        // dp[i] 表示整数i所能获得的最大拆分后乘积值;
        // dp[i] = for(int t=1; t<i; t++){max(t*(i-t), t*dp[i-t])};
        // dp[1] = 1;
        for(int i=1; i<=n; i++){
            for(int t=1; t<i; t++){
                dp[i] = max(dp[i], max(t*(i-t), t*dp[i-t]));
            }
        }
        return dp[n];
    }
};

相关推荐

  1. 算法记录 Day35

    2024-04-03 23:34:02       3 阅读
  2. 算法记录 Day33

    2024-04-03 23:34:02       2 阅读
  3. 算法记录 Day38

    2024-04-03 23:34:02       4 阅读
  4. 算法记录 Day36

    2024-04-03 23:34:02       2 阅读
  5. 算法记录 Day39

    2024-04-03 23:34:02       2 阅读
  6. 算法记录 Day37

    2024-04-03 23:34:02       2 阅读
  7. 算法day33

    2024-04-03 23:34:02       6 阅读
  8. 算法day32

    2024-04-03 23:34:02       5 阅读

最近更新

  1. leetcode705-Design HashSet

    2024-04-03 23:34:02       5 阅读
  2. Unity发布webgl之后打开streamingAssets中的html文件

    2024-04-03 23:34:02       5 阅读
  3. vue3、vue2中nextTick源码解析

    2024-04-03 23:34:02       6 阅读
  4. 高级IO——React服务器简单实现

    2024-04-03 23:34:02       5 阅读
  5. 将图片数据转换为张量(Go并发处理)

    2024-04-03 23:34:02       4 阅读
  6. go第三方库go.uber.org介绍

    2024-04-03 23:34:02       6 阅读
  7. 前后端AES对称加密 前端TS 后端Go

    2024-04-03 23:34:02       6 阅读

热门阅读

  1. VC++、GCC、CLANG,INT128有符号整数编译器关键字

    2024-04-03 23:34:02       4 阅读
  2. Python 抽象类

    2024-04-03 23:34:02       6 阅读
  3. 第六章:使用 kubectl 创建 Deployment

    2024-04-03 23:34:02       4 阅读
  4. vue3 + howuse, 实现echarts symbol使用 gif 动画图片

    2024-04-03 23:34:02       3 阅读
  5. 初识人工智能---------自然语言处理&&词袋模型

    2024-04-03 23:34:02       5 阅读
  6. MySQL学习笔记(持续更行ing)

    2024-04-03 23:34:02       7 阅读
  7. C++从入门到精通——nullptr

    2024-04-03 23:34:02       4 阅读
  8. 大厂HashMap源码面试

    2024-04-03 23:34:02       4 阅读
  9. Linux进程状态

    2024-04-03 23:34:02       4 阅读
  10. 力扣--哈希表+滑动子块--串联所有单词子串

    2024-04-03 23:34:02       4 阅读
  11. MySQL两表联查之分组成绩第几问题

    2024-04-03 23:34:02       4 阅读