?

步驟一、確定狀態(tài):

確定dp數(shù)組及下標(biāo)含義

dp數(shù)組是一維，大小是[6*n+1], 這里要注意下，背包的容量會(huì)和物品的重量 有關(guān)系了，投擲n枚的骰子，背包的容量范圍是[n,6n]，用2枚想一下，出現(xiàn)的 點(diǎn)數(shù)和會(huì)是[2,12]的范圍。 所以這里的大小可以是6? n+1， 而dp[j]表示的是 裝滿當(dāng)前的點(diǎn)數(shù)和j， 有多少種裝法，求的點(diǎn)數(shù)出現(xiàn)的次數(shù)。

步驟二、推斷狀態(tài)方程:

dp[j-1]+dp[j-2]+dp[j-3]+dp[j- 4]+dp[j-5]+dp[j-6]

dp[j] += dp[j-cur]

步驟三、規(guī)定初始條件:

初始條件:

全局初始化都是0， 而這里需要初始化第一枚骰子的情況，也就是dp[1]~dp[6]開(kāi)始的時(shí)候 都是1， 后面遍歷的時(shí)候從第二枚骰子開(kāi)始

步驟四、計(jì)算順序:

物品正向遍歷，從2開(kāi)始，容量逆序遍歷，這里由于背包的容量會(huì)和當(dāng)前是第 幾個(gè)物品有關(guān)系了，所以容量范圍6*i, i

class Solution:def dicesProbability(self, n: int) -> List[float]:# 初始化數(shù)組，拋擲n枚，點(diǎn)數(shù)和為j出現(xiàn)的次數(shù)為dp[j]dp = [0] * (6*n + 1)for j in range(1, 7):dp[j] = 1for i in range(2, n + 1): # 遍歷物品for j in range(6*i, i - 1, -1): # 遍歷背包容量dp[j] = 0for cur in range(1, 7):if j - cur < i - 1:breakdp[j] += dp[j - cur]res = []for j in range(n, 6*n + 1):res.append(dp[j]/6**n)return res

總結(jié)

以上是生活随笔為你收集整理的97. Leetcode 剑指 Offer 60. n个骰子的点数 (动态规划-背包问题)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。