中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當前位置: 首頁 > news >正文

網(wǎng)站頁面字體設置剛剛地震最新消息今天

網(wǎng)站頁面字體設置,剛剛地震最新消息今天,東莞服務36招全稱,大學生創(chuàng)新創(chuàng)業(yè)網(wǎng)站開發(fā)2140. 解決智力問題 - 力扣(LeetCode) 這道題是一個典型的 動態(tài)規(guī)劃(Dynamic Programming, DP) 問題,可以使用 自底向上 的方式解決。 思路 定義狀態(tài): 設 dp[i] 表示從第 i 題開始,能獲得的最高…

2140. 解決智力問題 - 力扣(LeetCode)

這道題是一個典型的 動態(tài)規(guī)劃(Dynamic Programming, DP) 問題,可以使用 自底向上 的方式解決。

思路

  1. 定義狀態(tài)
    dp[i] 表示從第 i 題開始,能獲得的最高分數(shù)。

  2. 狀態(tài)轉移方程

    • 選擇解決第 i
      • 這樣可以獲得 questions[i][0] 分,并且需要跳過 questions[i][1] 題。
      • 下一次可以從 i + questions[i][1] + 1 題開始,即 dp[i] = questions[i][0] + dp[i + questions[i][1] + 1]。
    • 選擇跳過第 i
      • 這樣可以從 i+1 題開始,即 dp[i] = dp[i+1]。
    • 取兩者的最大值: dp[i]=max?(questions[i][0]+dp[i+questions[i][1]+1],dp[i+1])
  3. 邊界條件

    • dp[n] = 0 (當超過最后一題時,得分為 0)。
  4. 計算順序

    • 我們需要從 后往前 計算 dp[i],因為 dp[i] 依賴于 dp[i+1]dp[i + questions[i][1] + 1]

代碼實現(xiàn)

from typing import Listdef mostPoints(questions: List[List[int]]) -> int:n = len(questions)dp = [0] * (n + 1)  # dp[i] 表示從第 i 題開始能獲得的最高分for i in range(n - 1, -1, -1):  # 逆序遍歷points, brainpower = questions[i]next_index = i + brainpower + 1  # 下一道可以解的題目dp[i] = max(points + (dp[next_index] if next_index < n else 0), dp[i + 1])return dp[0]

復雜度分析

  • 時間復雜度:O(n),我們只需遍歷 questions 一次,每次 O(1) 計算 dp[i]。
  • 空間復雜度:O(n),用于存儲 dp 數(shù)組。

示例

輸入
questions = [[3, 2], [4, 3], [4, 4], [2, 5]]
print(mostPoints(questions))
輸出
5

優(yōu)化(O(1) 空間)

我們可以只用一個變量來存儲 dp[i+1],這樣 dp 數(shù)組就不需要額外存儲所有狀態(tài):

def mostPoints(questions: List[List[int]]) -> int:n = len(questions)next_max = 0  # 相當于 dp[i+1]for i in range(n - 1, -1, -1):points, brainpower = questions[i]next_index = i + brainpower + 1current = max(points + (dp[next_index] if next_index < n else 0), next_max)next_max = current  # 更新 dp[i]return next_max

這樣,我們將 空間復雜度優(yōu)化為 O(1)。

http://www.risenshineclean.com/news/11444.html

相關文章:

  • 內部網(wǎng)站做域名解析到端口發(fā)布軟文
  • 怎么建設批量模板網(wǎng)站搜索引擎優(yōu)化是做什么
  • 網(wǎng)站強制字體wordpress百度推廣基木魚
  • 廣州做網(wǎng)站的長春網(wǎng)站建設制作
  • 做網(wǎng)站的機構免費域名解析平臺
  • 淄博外貿(mào)網(wǎng)站建設公司網(wǎng)站seo排名優(yōu)化軟件
  • 北京定制網(wǎng)站開發(fā)公司軍事新聞今日最新消息
  • 找人做網(wǎng)站需要注意網(wǎng)絡營銷的現(xiàn)狀分析
  • 集團做網(wǎng)站方案制作包含哪些方面如何制作自己的鏈接
  • wordpress 調用分類目錄描述金華seo扣費
  • 一個網(wǎng)站按鈕怎么做圖片優(yōu)化
  • 網(wǎng)站優(yōu)化工作怎么樣seo和點擊付費的區(qū)別
  • 可以做皮膚測試的網(wǎng)站關鍵詞排名優(yōu)化如何
  • 網(wǎng)站建設找蓋亞科技營銷網(wǎng)站模板
  • 證件照制作免費版優(yōu)化網(wǎng)站seo策略
  • 如何提高網(wǎng)站點擊率怎么做合肥百度seo代理
  • 中國建設銀行余額查詢入口seo推廣人員
  • 網(wǎng)站在香港能備案嗎沈陽seo關鍵詞
  • 杭州品牌網(wǎng)站開發(fā)東莞網(wǎng)站推廣的公司
  • 2018做論壇網(wǎng)站好嗎百度推廣工作好干嗎
  • 網(wǎng)站制作公司排行榜建設網(wǎng)站
  • 營銷型網(wǎng)站開發(fā)泰安網(wǎng)站制作推廣
  • 網(wǎng)站建設制作設計推廣優(yōu)化國產(chǎn)十大erp軟件
  • 記賬代理公司注冊網(wǎng)絡seo優(yōu)化推廣
  • 昌吉網(wǎng)站建設哪家便宜seo站外優(yōu)化平臺
  • java php開發(fā)網(wǎng)站建設收錄入口在線提交
  • 公司網(wǎng)站建設技術方案模板免費創(chuàng)建個人網(wǎng)頁
  • 響應式手機網(wǎng)站制作西安seo顧問
  • 微信建立免費網(wǎng)站嗎360優(yōu)化大師官網(wǎng)
  • apache和wordpress網(wǎng)站seo關鍵詞優(yōu)化排名