欧美三区_成人在线免费观看视频_欧美极品少妇xxxxⅹ免费视频_a级毛片免费播放_鲁一鲁中文字幕久久_亚洲一级特黄

劍指offer 14.剪繩子 Python解法

系統 1913 0

題目描述:

給你一根長度為 n 繩子,請把繩子剪成 m 段(m、n 都是整數,2≤n≤58 并且 m≥2)。 每段的繩子的長度記為k[0]、k[1]、……、k[m]。k[0]k[1] … k[m] 可能的最大乘積是多少?

例如:當繩子的長度是8時,我們把它剪成長度分別為2、3、3的三段,此時得到最大的乘積18。

分析:

書上說的有數學規律:(看注釋)

            
              # 方法一:貪婪算法
def maxProductAfterCutting(length):
    if length == 2:                   # 這3個特殊的長度,直接求出返回值
        return 1
    elif length == 3:
        return 2
    elif length == 4:
        return 4
    c=[]
    while length >= 5:               # 由數學計算得出,當長度大于5時候,每段長3,乘積最大
        length-=3                    # 巧的是,如果最后剩4,分成2*2 乘積最大,但是4正好是2*2的值。巧!
        c.append(3)
    return 3**len(c)*length

maxProductAfterCutting(6)
            
          

方法二:動態規劃。把前邊的都求出來。

(從此題首次接觸動態規劃。)

            
              # 方法二:動態規劃
def dynamic_programming(n):
    if n==2:                         # 這3個特殊的長度,直接求出返回值
        return 1
    if n==3:
        return 2
    if n==4:
        return 4
    tem_lis = [0,0,2,3,4]                 # 這個列表的前兩個數無所謂,因為根本用不到
    
    for i in range(5,n+1):                # 外循環:繩子長度從5到n  注意range()前閉后開。
        maxx = 0 
        for j in range(2,i//2+1):         # 內循環:所有可能的組合:2,3,4...中間值
            tem = tem_lis[j]*tem_lis[i-j] # i-j 為另一段長度
            if tem > maxx:
                maxx = tem                # maxx存放乘積最大的值
        tem_lis.append(maxx)              # tem_list中存儲的是所有的可能繩子長度的解
    #print(tem_lis)
    return tem_lis[n]

dynamic_programming(8)
                
            
          

?


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: xxnxx中国18| 国产亚洲精品不卡在线 | 一本大道香蕉中文日本不卡高清二区 | 搡女人的高清免费视频 | 91精品国产乱码久久久久久久久 | 亚洲区视频 | 久久久久成人精品 | 免费中文字幕视频 | 97精品国产| 久久精品视频网站 | 日韩午夜影院 | 午夜视频在线免费播放 | 亚洲成av人片在线观看 | 久久久久久99 | 成人精品国产 | 日本美女一区二区 | 欧美一区二区精品 | 久草五月天| 日韩欧美一区二区三区不卡在线 | 国产精品久久久久久久久久久新郎 | 妞干在线 | 操出白浆在线观看 | 久久精品23| 天天干天天操天天射 | 日本高清va不卡视频在线观看 | 日日草夜夜操 | 一区二区国产精品 | 亚洲天天做日日做天天看2018 | 久久久视频在线 | 成人国产精品免费视频不卡 | 国产你懂得 | 毛片在线免费观看完整版 | 亚洲综合一二三区 | 一区在线免费观看 | 香港三级日本三级a视频 | 欧美日韩亚洲一区 | 五月色丁香综缴合 | 欧美国产日韩在线观看 | 91国内精品久久久久免费影院 | 成人啪啪网站 | 一区二区免费在线 |