草庐IT

代码随想录|day41| 动态规划part03● 343. 整数拆分 ● 96.不同的二叉搜索树

isabelightL 2023-07-26 原文

今天两题都挺有难度，建议大家思考一下没思路，直接看题解，第一次做，硬想很难想出来。

  343. 整数拆分

链接：代码随想录

视频讲解很详细，链接动态规划，本题关键在于理解递推公式！| LeetCode：343. 整数拆分_哔哩哔哩_bilibili

 

class Solution {
public:
/*使这些整数的乘积最大化,乘积最大化没有见过，没思路
//看了讲解
dp[i] 意味着对数字i进行拆分后，拆分数的最大值
拆成2个数， j, i-j。 
拆成3个或者3个以上的数，j, dp[i-j](个数未知)

初始值,dp[0]----------------对0拆分无意义
       dp[1]-----------------1*1=1
       dp[2]-----------------1*2=1
       dp[3]-----------------1*3 2*dp[1]-------3
*/

    int integerBreak(int n) {
        vector<int>dp(n+1,0);
        dp[2]=1;
        for(int i=3;i<=n;i++)//拆分2、拆分3、。。。。拆分n
        {
            for(int j=1;j<=i/2;j++)
            {
                dp[i]=max(max(j*(i-j),j*dp[i-j]),dp[i]);
            }
        }
        return dp[n];
    }
};

 注意：我在这里犯了两个错，有两个不好理解的点，一是更新最大值的时候要跟上一个dp[i]

一、对比更新，所以最后的递推式写出来要比较三个数：

1、拆分成两个数的j*(i-j)

2、拆分成多个数的j*dp[i-j]

3、每一轮终需要更新的dp[i]

二、截取的j，要从1-i/2, 而不是j*j<=i.

反例：

这里按照j<=i/2，j=1,2,3.

按照j*j<=i，j=1,2 

96.不同的二叉搜索树 

链接：代码随想录

 自己实在想了一堆非常废的想法，外加我现在很困很困。。。。呜呜呜昨天应该早点睡，但是睡了又怕起不来。

在卡哥的角度，这道题以n=3为例子进行讲解。

可以看成以1为根节点、以2为根节点、以3为根节点 的 组合。

 

 这道题显然是从0、1、2从小到大推3

dp[i]代表节点个数为i时，树的种类数为dp[i]

则以j为节点,j左子树的节点为1到j-1,共j-1个；

                    j 右子树的节点为j+1到i,左闭右闭,共i-j个。

即以j为节点，dp[i]=dp[j-1]*dp[i-j]

同时j可以是0、1、2...n,故dp[i]是所有情况的累加。

//动态规划初始值
dp[0]=1;//------------------空树也算是树的一种情况，如果等于0那么乘以任何数都为0了
dp[1]=1;//------------------n=1时dp[1]
dp[2]=2;
for(int i=3;i<=n;i++)
{
  for(int j=1;j<=i;j++)
{
  dp[i]+=dp[j-1]*dp[i-j];
}

}
return dp[n];

不知道为什么自己写的答案报了overflow(因为如果n=1,根本不可能出现dp[2]，我这算是提前写了dp[2])

正确答案：

class Solution {
public:
    int numTrees(int n) {
       vector<int>dp(n+1,0);
//动态规划初始值
     if(n==0||n==1)
     {
       return 1;
     }
     // n>1，则必定出现dp[0]\dp[1]
      dp[0]=1;//------------------空树也算是树的一种情况
      dp[1]=1;//------------------n=1时dp[1]
      for(int i=2;i<=n;i++)
    {
      for(int j=1;j<=i;j++)
    {
      dp[i]+=dp[j-1]*dp[i-j];
    }
    cout<<i<<"   "<<dp[i]<<endl;
    }
    return dp[n];
    }
};

随想录partxff0cxffxff0算法数据结构

有关代码随想录|day41| 动态规划part03● 343. 整数拆分 ● 96.不同的二叉搜索树的更多相关文章

  1. ruby - 如何在 Ruby 中拆分参数字符串 Bash 样式？ - 2

    我正在为一个项目制作一个简单的shell，我希望像在Bash中一样解析参数字符串。foobar"helloworld"fooz应该变成:["foo","bar","helloworld","fooz"]等等。到目前为止，我一直在使用CSV::parse_line，将列分隔符设置为""和.compact输出。问题是我现在必须选择是要支持单引号还是双引号。CSV不支持超过一个分隔符。Python有一个名为shlex的模块:>>>shlex.split("Test'helloworld'foo")['Test','helloworld','foo']>>>shlex.split('Test"

  2. ruby-on-rails - Nokogiri:使用 XPath 搜索 <div> - 2

    我使用Nokogiri(Rubygem)css搜索寻找某些在我的html里面。看起来Nokogiri的css搜索不喜欢正则表达式。我想切换到Nokogiri的xpath搜索，因为这似乎支持搜索字符串中的正则表达式。如何在xpath搜索中实现下面提到的(伪)css搜索？require'rubygems'require'nokogiri'value=Nokogiri::HTML.parse(ABBlaCD3"HTML_END#my_blockisgivenmy_bl="1"#my_eqcorrespondstothisregexmy_eq="\/[0-9]+\/"#FIXMEThefoll

  3. ruby - 如何搜索有用的 ruby - 2

    寻找有用的ruby的好网站是什么？ 最佳答案 AgileWebDevelopment列出插件(虽然不是ruby​​gems，我不确定为什么)，并允许人们对它们进行评级。RubyToolbox按类别列出gem并比较它们的受欢迎程度。Rubygems有一个搜索框。StackOverflow对最有用的rails插件和ruby​​gems有疑问。 关于ruby-如何搜索有用的ruby，我们在StackOverflow上找到一个类似的问题： https://stacko

  4. ruby - 如何搜索、递增和替换 Ruby 字符串中的整数子字符串？ - 2

    我有很多这样的文档:foo_1foo_2foo_3bar_1foo_4...我想通过获取foo_[X]的所有实例并将它们中的每一个替换为foo_[X+1]来转换它们。在这个例子中:foo_2foo_3foo_4bar_1foo_5...我可以用gsub和一个block来做到这一点吗？如果不是，最干净的方法是什么？我真的在寻找一个优雅的解决方案，因为我总是可以暴力破解它，但我觉得有一些正则表达式技巧值得学习。 最佳答案 我(完全)不懂Ruby，但类似这样的东西应该可以工作:"foo_1foo_2".gsub(/(foo_)(\d+)/

  5. ruby - Ruby 中的必应搜索 API - 2

    我读了"BingSearchAPI-QuickStart"但我不知道如何在Ruby中发出这个http请求(Weary)如何在Ruby中翻译“Stream_context_create()”？这是什么意思？"BingSearchAPI-QuickStart"我想使用RubySDK，但我发现那些已被弃用前(Rbing)https://github.com/mikedemers/rbing您知道Bing搜索API的最新包装器(仅限Web的结果)吗？ 最佳答案 好吧，经过一个小时的挫折，我想出了一个办法来做到这一点。这段代码很糟糕，因为它是

  6. Ruby#index 方法 VS 二进制搜索 - 2

    给定一个元素和一个数组，Ruby#index方法返回元素在数组中的位置。我使用二进制搜索实现了我自己的索引方法，期望我的方法会优于内置方法。令我惊讶的是，内置的在实验中的运行速度大约是我的三倍。有Rubyist知道原因吗？ 最佳答案 内置#indexisnotabinarysearch，这只是一个简单的迭代搜索。但是，它是用C而不是Ruby实现的，因此自然可以快几个数量级。 关于Ruby#index方法VS二进制搜索，我们在StackOverflow上找到一个类似的问题：

  7. ruby - 在 Ruby 中实现二叉树 - 2

    我一直在尝试在Ruby中实现BinaryTree类，但我得到了stackleveltoodeep错误，尽管我似乎没有在该特定代码段中使用任何递归:1.classBinaryTree2.includeEnumerable3.4.attr_accessor:value5.6.definitialize(value=nil)7.@value=value8.@left=BinaryTree.new#stackleveltoodeephere9.@right=BinaryTree.new#andhere10.end11.12.defempty?13.(self.value==nil)?true:

  8. ruby - 拆分字符串并分配给不同的变量 - 2

    我从ui中得到日期范围为-approved_between"=>"2013-03-17-2013-03-18"我需要拆分此approved_start_date="2013-03-17"和approved_end_date="2013-03-18"...我希望使用它在mysql中查询，因为mysql中的日期格式是created_at:2012-07-2810:35:01.我正在做的是:approved=approved_between.split("")approved_start_date=approved[0]approved_end_date=approved[2]很确定这不是处

  9. ruby-on-rails - Ruby on Rails 将列表拆分或切片为列 - 2

    @locations=Location.all#currentlistingall@locations=Location.slice(5)orLocation.split(5)使用Ruby，我试图将我的列表分成4列，每列限制为5个；然而，切片或拆分似乎都不起作用。知道我可能做错了什么吗？任何帮助是极大的赞赏。 最佳答案 您可能想使用in_groups_of:http://railscasts.com/episodes/28-in-groups-of这是RyanBates在railscast中的示例用法:

  10. ruby-on-rails - rails : Find tasks that were created on a certain day? - 2

    我有一个任务列表(名称、starts_at)，我试图在每日View中显示它们(就像iCal)。deftodays_tasks(day)Task.find(:all,:conditions=>["starts_atbetween?and?",day.beginning,day.ending]end我不知道如何将Time.now(例如“2009-04-1210:00:00”)动态转换为一天的开始(和结束)，以便进行比较。 最佳答案 deftodays_tasks(now=Time.now)Task.find(:all,:conditio

随机推荐