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

確定dp數(shù)組及含義 dp[i]表示的是i個(gè)數(shù)里面循環(huán)刪除m個(gè)數(shù)剩下的數(shù)

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

首先假設(shè)f(n,m)表示從n個(gè)數(shù)字0....n?1中每次刪除第 m個(gè)數(shù)字之后剩下的數(shù)字。 那么在這n個(gè)數(shù)字中， 第 一個(gè)被刪除的是 (m?1)%n，假設(shè)這個(gè)數(shù)用k表示，那 么刪除k剩下的n?1個(gè)數(shù)字0 , 1 , . . k ? 1 , k +1 , . . . n ? 1 ，并且下一次要從k+1開(kāi)始計(jì)數(shù)。那么 我們假設(shè)再換成上面那種方式，把k+1映射成0，k+2 映射成1，...那這樣這個(gè)問(wèn)題就和上面那個(gè)一樣了，這 個(gè)新問(wèn)題就變成了從n?1個(gè)數(shù)字0...n?2中每次刪除第 m個(gè)數(shù)字之后剩下的數(shù)字，記這個(gè)為f ′ (n?1,m)。注 意這個(gè)f ′ 和前面f不是一個(gè)函數(shù)了，經(jīng)過(guò)了映射。顯 然，最初序列最后剩下的數(shù)字一定是刪除一個(gè)數(shù)字之 后序列最后剩下的數(shù)字，即f(n?1,m)=f ′ (n?1,m)

?

?

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

初始條件: dp[1]=0

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

i從2到n遍歷

class Solution:def lastRemaining(self, n: int, m: int) -> int:dp = [0] * (n+1)dp[1] = 0for i in range(2, n+1):dp[i] = (m+dp[i-1])%ireturn dp[-1]

?

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的90. Leetcode 剑指 Offer 62. 圆圈中最后剩下的数字 (动态规划-基础题)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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