70. 爬楼梯 - 力扣（LeetCode）
dp[i]表示走到第i阶有的方法 ，一次可以爬1个或2个台阶，所以每次可以由前一个或前2个台阶转移过来
func climbStairs(n int) int {
dp := make([]int,n+2)
dp[0] = 1
dp[1] = 1
dp[2] = 1
for i := 2; i <= n; i ++ {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}198. 打家劫舍 - 力扣（LeetCode）
寻找子问题 选择 dp[i] 表示前i个房屋能够偷窃到的最高金额 根据是否偷第i个房屋 可以把问题转化为dp[i-1]和dp[i-2]
func rob(nums []int) int {
//取前一个的话，当前就不能取了
//取前两个的话 可以取当前的元素
n := len(nums)
dp := make([]int,n+2)
//dp[i] 表示前i个房屋能够偷窃到的最高金额
dp[1] = nums[0]
for i := 2; i <= n; i ++ {
dp[i] = max(dp[i-1],dp[i-2] + nums[i-1])
}
return dp[n]
}139. 单词拆分 - 力扣（LeetCode）
dp[i]表示前i个字符是否可以由单词构成
枚举上一个单词是多少
如果存在的话，就从dp[j-1]转移过来！！记住是j-1，因为j这个地方被看作一个单词了
func wordBreak(s string, wordDict []string) bool {
n := len(s)
s = " " + s
dp := make([]bool,n+2)
mp := make(map[string]struct{})
for _,word := range wordDict {
mp[word] = struct{}{}
}
dp[0] = true
for i := 1; i <= n; i ++ {
//枚举上一个单词
for j := i; j >= 1; j -- {
// fmt.Println(i,s[j:i+1])
if _,ok := mp[s[j:i+1]]; ok {
if dp[j-1] {
dp[i] = true
}
//dp[i] |= dp[j]
}
}
}
//fmt.Println(dp)
return dp[n]
}322. 零钱兑换 - 力扣（LeetCode）
dp[i] 表示构成总金额为i的最少硬币个数
看这个硬币选哪个
func coinChange(coins []int, amount int) int {
// n := len(coins)
dp := make([]int, amount+2)
for i := 0; i <= amount; i++ {
dp[i] = 1000000000
}
dp[0] = 0
for i := 1; i <= amount; i++ {
for _, coin := range coins {
if i-coin < 0 {
continue
}
dp[i] = min(dp[i], dp[i-coin]+1)
}
}
if dp[amount] != 1000000000 {
return dp[amount]
}
return -1
}300. 最长递增子序列 - 力扣（LeetCode）
dp[i] 表示在前i个元素里选 并且以nums[i]结尾的最长递增子序列的长度
因为不选第i个元素的话 ，其实答案就在前面更新过了，所以每次都只需要考虑选第i个元素的情况
func lengthOfLIS(nums []int) int {
n := len(nums)
dp := make([]int,n+2)
ans := 1
for i := 1; i <= n; i ++ {
dp[i] = 1
for j := i - 1; j >= 1; j -- {
if nums[i-1] > nums[j-1] {
dp[i] = max(dp[i],dp[j] + 1)
}
}
ans = max(ans,dp[i])
}
return ans
}类似贪心的思想，首先维护答案这个单调递增的队列，其次，贪心的考虑，如何使得这个队列最长，如果是nums[i]大于队尾的数的话，直接拼接；否则，就二分找第一个大于等于nums[i]的数替换，这样可以使得后面的数更有概率接上
func lengthOfLIS(nums []int) int {
var q []int
// var cnt int = 0
q = append(q,nums[0])
check := func(x int) int {
ans,l,r := len(q)-1,0,len(q)-1
for l <= r {
mid := (l+r) / 2
if q[mid] >= x {
ans = mid
r = mid - 1
}else{
l = mid + 1
}
}
return ans
}
for i := 1; i < len(nums); i ++ {
if nums[i] > q[len(q)-1] {
//直接拼接
q = append(q,nums[i])
}else{
//找到第一个大于等于nums[i]的数 替换
q[check(nums[i])] = nums[i]
}
}
return len(q)
}120. 三角形最小路径和 - 力扣（LeetCode）
注意一开始dp[i][j]都要初始化为最大值，防止错误的边界转移。初始化是dp[0][0]
func minimumTotal(triangle [][]int) int {
n := len(triangle)
dp := make([][]int,n+1)
for i := 0; i <= n; i ++ {
dp[i] = make([]int,n+1)
for j := 0; j < n + 1; j ++ {
dp[i][j] = 100000000
}
}
dp[0][0] = triangle[0][0]
for i := 1; i < n; i ++ {
for j := 0; j < len(triangle[i]); j ++ {
dp[i][j] = dp[i-1][j] + triangle[i][j]
if j - 1 >= 0 && dp[i][j] > dp[i-1][j-1] + triangle[i][j] {
dp[i][j] = dp[i-1][j-1] + triangle[i][j]
}
}
}
// for i := 0 ; i < len(dp); i ++ {
// fmt.Println(dp[i])
// }
ans := dp[n-1][0]
for i := 1; i < len(triangle[n-1]); i ++ {
if ans > dp[n-1][i] {
ans = dp[n-1][i]
}
}
return ans
}64. 最小路径和 - 力扣（LeetCode）
dp[i][j]表示从左上角走到(i,j)位置可以获得的最小路径的和，转移的话就是可以从左边或上边转移过来
func min(a,b int) int {
if a < b {
return a
}
return b
}
func minPathSum(grid [][]int) int {
n,m := len(grid), len(grid[0])
dp := make([][]int,n+1)
for i := 0; i < n; i ++ {
dp[i] = make([]int,m+1)
for j := 0; j < m; j ++ {
dp[i][j] = 200 * 200 + 100
}
}
dp[0][0] = grid[0][0]
for i := 1; i < m; i ++ {
dp[0][i] = dp[0][i-1] + grid[0][i]
}
for i := 1; i < n; i ++ {
dp[i][0] = dp[i-1][0] + grid[i][0]
}
for i := 1; i < n; i ++ {
for j := 1; j < m; j ++ {
dp[i][j] = min(dp[i][j-1],dp[i-1][j]) + grid[i][j]
}
}
// for i := 0; i < n; i ++ {
// fmt.Println(dp[i])
// }
return dp[n-1][m-1]
}63. 不同路径 II - 力扣（LeetCode）
dp[i][j] 表示走到(i,j)的路径数量 注意初始化初始化初始化！
第一行和第一列都需要从0开始遍历，如果遇到障碍物就跳出
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
n,m := len(obstacleGrid),len(obstacleGrid[0])
dp := make([][]int,n+1)
for i := 0; i < n + 1; i ++ {
dp[i] = make([]int,m+1)
}
for i := 0; i < n; i ++ {
if obstacleGrid[i][0] == 1 {
break
}
dp[i][0] = 1
}
for j := 0; j < m; j ++ {
if obstacleGrid[0][j] == 1 {
break
}
dp[0][j] = 1
}
for i := 1; i < n; i ++ {
for j := 1; j < m; j ++ {
if obstacleGrid[i][j] != 1 {
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
}
return dp[n-1][m-1]
}5. 最长回文子串 - 力扣（LeetCode）
dp[start][end]表示字符串s[start:end]是否为回文子串
如果长度为2的话，只需要判断strart和end是否相等
如果长度大于2的话，需要判断start和end是否相等，以及[start+1:end]是否为回文子串
func longestPalindrome(s string) string {
n := len(s)
s = " " + s
dp := make([][]int,n+2)
for i := 0; i < n + 2; i ++ {
dp[i] = make([]int,n+2)
dp[i][i] = 1
}
var ans string = string(s[1])
for length := 2; length <= n; length ++ {
for start := 1; start + length - 1 <= n; start ++ {
end := start + length - 1
if length == 2 {
if s[start] == s[end] {
dp[start][end] = 1
}
}else{
if s[start] == s[end] && dp[start + 1][end-1] == 1 {
dp[start][end] = 1
}
}
if dp[start][end] == 1 && len(ans) < length {
ans = s[start:end+1]
}
}
}
return ans
}97. 交错字符串 - 力扣（LeetCode）
s1的前i个字符和s2的前j个字符能否构成s3的前i+j个字符
func isInterleave(s1 string, s2 string, s3 string) bool {
if len(s1) + len(s2) != len(s3) {
return false
}
if len(s1) == 0 && s2 != s3 {
return false
}
if len(s2) == 0 && s1 != s3 {
return false
}
n,m := len(s1),len(s2)
s1 = " " + s1
s2 = " " + s2
s3 = " " + s3
dp := make([][]int,n+2)
for i := 0; i < n+2; i ++ {
dp[i] = make([]int,m+2)
}
//s1的前i个字符和s2的前j个字符能否构成s3的前i+j个字符
for i := 0; i <= n; i ++ {
for j := 0; j <= m; j ++ {
if s1[i] == s3[i+j] {
//s1的第i个字符当s3的第i+j个字符
if i == 0 {
dp[i][j] = 1
}else{
dp[i][j] = dp[i-1][j]
}
}
if s2[j] == s3[i+j] {
//s2的第j个字符当s3的第i+j个字符
if j == 0 {
dp[i][j] = 1
}else{
if dp[i][j] == 1 || dp[i][j-1] == 1 {
dp[i][j] = 1
}
}
}
}
}
return dp[n][m] == 1
}72. 编辑距离 - 力扣（LeetCode）
dp[i][j]表示 word1的前i个字符变为word2的前j个字符需要的最少操作数
如果word1[i] == word2[j]的话，说明word2的第j个字符不需要做操作。否则，考虑操作
替换操作：直接把word1[i]换为word2[j]，上一个状态就是dp[i-1][j-1]
删除操作：相当于把word1[i]删除，上一个状态就是dp[i-1][j]
func min(a,b int) int {
if a < b {
return a
}
return b
}
func minDistance(word1 string, word2 string) int {
n,m := len(word1),len(word2)
dp := make([][]int,n+2)
for i := 0; i < n + 2; i ++ {
dp[i] = make([]int,m+2)
for j := 0; j < m + 2; j ++ {
dp[i][j] = 500*500
}
}
word1 = " " + word1
word2 = " " + word2
//word1的前i个字符变为word2的前j个字符需要的最少操作数
for i := 0; i <= n; i ++ {
dp[i][0] = i
}
for i := 0; i <= m; i ++ {
dp[0][i] = i
}
for i := 1; i <= n; i ++ {
for j := 1; j <= m; j ++ {
if word1[i] == word2[j] {
dp[i][j] = min(dp[i][j],dp[i-1][j-1])
}
//替换
dp[i][j] = min(dp[i][j],dp[i-1][j-1] + 1 )
// 插入 第i个字符是插入的
dp[i][j] = min(dp[i][j],dp[i][j-1] + 1)
// 删除
dp[i][j] = min(dp[i][j],dp[i-1][j] + 1 )
}
}
return dp[n][m]
}221. 最大正方形 - 力扣（LeetCode）
dp[i][j] 表示以(i,j)为右下角的最大正方形边长
func min(a,b int) int {
if a < b {
return a
}
return b
}
func max(a,b int) int {
if a > b {
return a
}
return b
}
func maximalSquare(matrix [][]byte) int {
//dp[i][j] 表示以(i,j)为右下角的最大正方形边长
n,m := len(matrix),len(matrix[0])
dp := make([][]int,n+2)
for i := 0; i < n+2; i ++ {
dp[i] = make([]int,m+2)
}
ans := 0
for i := 1; i <= n; i ++ {
for j := 1; j <= m; j ++ {
if matrix[i-1][j-1] == '1' {
dp[i][j] = min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1])) + 1
}else{
dp[i][j] = 0
}
ans = max(ans,dp[i][j])
}
}
return ans * ans
}118. 杨辉三角 - 力扣（LeetCode）
本质上是递推，关键是处理j=0和j=i的边界
func generate(numRows int) [][]int {
dp := make([][]int,numRows)
dp[0] = []int{1}
for i := 1; i < numRows; i ++ {
dp[i] = make([]int,i+1)
for j := 0; j <= i; j ++ {
if j == 0 {
dp[i][j] = dp[i-1][j]
}else if j == i {
dp[i][j] = dp[i-1][j-1]
}else{
//dp[1][1] = dp[0][0] + dp[0][1]
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
}
}
}
return dp
}279. 完全平方数 - 力扣（LeetCode）
拆分子问题：i-x 其中x是完全平方数 ,dp[i]表示和为i的完全平方数的最少数量
func numSquares(n int) int {
dp := make([]int,n+1)
for i := 0 ; i < n + 1; i ++ {
dp[i] = 1000000
}
dp[0] = 0
for i := 1; i <= n; i ++ {
for j := 1; j * j <= i; j ++ {
dp[i] = min(dp[i],dp[i-j*j]+1)
}
}
return dp[n]
}152. 乘积最大子数组 - 力扣（LeetCode）
dpMax[i] 表示以第i个元素结尾的最大乘积
dpMin[i] 表示以第i个元素结尾的最小乘积
func maxProduct(nums []int) int {
//连续
//选这个数 不选这个数
n := len(nums)
dpMax,dpMin := make([]int,n+2), make([]int,n+2)
dpMax[0],dpMin[0] = nums[0],nums[0]
ans := nums[0]
for i := 1; i < n; i ++ {
dpMax[i] = max(dpMax[i-1] * nums[i],max(dpMin[i-1] * nums[i], nums[i]))
dpMin[i] = min(dpMax[i-1] * nums[i],min(dpMin[i-1] * nums[i], nums[i]))
ans = max(ans,dpMax[i])
}
return ans
}416. 分割等和子集 - 力扣（LeetCode）
问题转化为：能否选出一批元素使得和为sum/2 。dp[i][j]表示从前i个元素里选 能否构成和为sum
子问题是：不选当前元素 和 选择当前元素
func canPartition(nums []int) bool {
//能否选出一批元素使得和为sum/2
sum,n := 0, len(nums)
for i := 0; i < n; i ++ {
sum += nums[i]
}
if sum % 2 != 0 {
return false
}
sum = sum / 2
dp := make([][]bool,n+2)
for i := 0; i < n + 2; i ++ {
dp[i] = make([]bool,sum+2)
}
//dp[i][j]表示从前i个元素里选 能否构成和为sum的
dp[0][0] = true
for i := 1; i <= n; i ++ {
for j := 0; j <= sum ; j ++ {
//不选当前元素
dp[i][j] = dp[i-1][j]
if j - nums[i-1] >= 0 {
//选当前元素
if dp[i][j] || dp[i-1][j-nums[i-1]] {
dp[i][j] = true
}
// dp[i][j] |= dp[i-1][j-nums[i-1]]
}
}
if dp[i][sum] {
return true
}
}
return false
}62. 不同路径 - 力扣（LeetCode）
dp[i][j] 表示走到(i,j)的不同路径条数
func max(a, b int) int {
if a > b {
return a
}
return b
}
func uniquePaths(m int, n int) int {
//有多少条不同的路径
dp := make([][]int, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int, n+1)
}
dp[1][1] = 1
for i := 2; i <= m; i++ {
dp[i][1] = 1
}
for i := 2; i <= n; i++ {
dp[1][i] = 1
}
for i := 2; i <= m; i++ {
for j := 2; j <= n; j++ {
dp[i][j] += dp[i-1][j] + dp[i][j-1]
}
}
return dp[m][n]
}1143. 最长公共子序列 - 力扣（LeetCode）
dp[i][j]表示text1[:i] 和 text2[:j]的最长公共子序列长度
func longestCommonSubsequence(text1 string, text2 string) int {
/*
子问题：看text1[i]是否能和text2[j]匹配上
如果相等的话 就都选择
不相等的话 只能选一个
*/
n,m := len(text1), len(text2)
text1 = " " + text1
text2 = " " + text2
dp := make([][]int,n+2)
for i := 0 ; i < n + 2; i ++ {
dp[i] = make([]int,m+2)
}
//dp[i][j]表示text1[:i] 和 text2[:j]的最长公共子序列长度
for i := 1; i <= n ;i ++ {
for j := 1; j <= m; j ++ {
if text1[i] == text2[j] {
dp[i][j] = dp[i-1][j-1] + 1
}else{
dp[i][j] = max(dp[i-1][j],dp[i][j-1])
}
}
}
return dp[n][m]
}32. 最长有效括号 - 力扣（LeetCode）
func longestValidParentheses(s string) int {
//dp[i] 表示 前i个字符里 最长有效子串的长度
n := len(s)
dp := make([]int,n+2)
ans := 0
for i := 1; i < n; i ++ {
if s[i] == ')' {//当前字符是右括号
if s[i-1] == '(' {
//上一个字符是左括号
if i - 2 >= 0 {
dp[i] = dp[i-2] + 2
}else{
dp[i] = 2
}
}else{//上一个字符是右括号 找到上一个字符配对的左括号位置pos，看pos-1能否和i匹配
if i-dp[i-1]-1 >= 0 && s[i-dp[i-1]-1] == '(' {
//配对了
if i-dp[i-1]-2 >= 0 {//注意这里的处理
dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2
}else{
dp[i] = dp[i-1] + 2
}
}
}
}
ans = max(ans,dp[i])
}
return ans
}LCR 126. 斐波那契数 - 力扣（LeetCode）
dp[i]表示第i个斐波那契数的值
func fib(n int) int {
const MAXN = 1000000007
dp := make([]int,n+2)
dp[0] = 0
dp[1] = 1
for i := 2; i <= n; i ++ {
dp[i] = (dp[i-1] + dp[i-2]) % MAXN
}
return dp[n]
}LCR 127. 跳跃训练 - 力扣（LeetCode）
也是一个递推流程，注意dp[0] = 1
func trainWays(num int) int {
const MAXN = 1000000007
dp := make([]int,num+3)
dp[0] = 1
dp[1] = 1
dp[2] = 2
for i := 3; i <= num; i ++ {
dp[i] = (dp[i-1] + dp[i-2]) % MAXN
}
return dp[num]
}LCR 188. 买卖芯片的最佳时机 - 力扣（LeetCode）
第i天可以获得的价值是第i天的价格减去前面i-1天的最小值
func bestTiming(prices []int) int {
if len(prices) == 0 {
return 0
}
minn := prices[0]
ans := 0
for i := 1; i < len(prices); i ++ {
ans = max(ans,prices[i] - minn)
minn = min(minn,prices[i])
}
return ans
}LCR 161. 连续天数的最高销售额 - 力扣（LeetCode）
维护当前的最大值和答案即可，对于每天的销售额，有2种选择：跟上一天的拼接，单独另起一段
func maxSales(sales []int) int {
var ans int = -1000000000
now := 0
for _,sale := range sales {
now = max(now+ sale,sale)
ans = max(now,ans)
}
return ans
}LCR 166. 珠宝的最高价值 - 力扣（LeetCode）
网格图dp，dp[i][j]表示走到[i,j]能够获得的最高价值
func max(a, b int) int {
if a > b {
return a
}
return b
}
func jewelleryValue(frame [][]int) int {
//每次可以移动到右侧或下侧的相邻位置
n, m := len(frame), len(frame[0])
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, m+1)
}
//初始化
dp[0][0] = frame[0][0]
for i := 1; i < n; i++ {
dp[i][0] = dp[i-1][0] + frame[i][0]
}
for i := 1; i < m; i ++ {
dp[0][i] = dp[0][i-1] + frame[0][i]
}
for i := 1; i < n; i++ {
for j := 1; j < m; j++ {
//可以从上面或是左边转移过来
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + frame[i][j]
}
}
return dp[n-1][m-1]
}LCR 165. 解密数字 - 力扣（LeetCode）
import "strconv"
func crackNumber(ciphertext int) int {
/*
子问题：第i位数字独立作为一种 和前一位数字作为一种
*/
s := strconv.Itoa(ciphertext)
//fmt.Println(s)
n := len(s)
s = " " + s
dp := make([]int,n+2)
dp[0] = 1
for i := 1; i <= n; i ++ {
//一位或两位
dp[i] = dp[i-1]
//如果可以2位的话 就2位
num,_ := strconv.Atoi(s[i-1:i+1])
if i - 2 >= 0 && num >= 10 && num <= 25 {
dp[i] += dp[i-2]
}
}
return dp[n]
}LCR 167. 招式拆解 I - 力扣（LeetCode）
las表示前面出现过的字符的最近位置，注意map的下标尽量从1开始
func dismantlingAction(arr string) int {
mp := make(map[rune]int)
ans := 0
las := 0
for i,ch := range arr {
las = max(las,mp[ch])
ans = max(ans,i-las + 1 )
mp[ch] = i + 1
}
return ans
}LCR 168. 丑数 - 力扣（LeetCode）
每个丑数可以由之前的数乘以2或乘以3或乘以5得到，分别维护三个指针，每次取最小的作为第i个整数
func nthUglyNumber(n int) int {
dp := make([]int,n+2)
dp[1] = 1
cnt2,cnt3,cnt5 :=1,1,1
for i := 2; i <= n; i ++ {
dp[i] = min(dp[cnt2] * 2, min(dp[cnt3] * 3, dp[cnt5] * 5 ) )
if dp[i] == dp[cnt2] * 2 {
cnt2 ++
}
if dp[i] == dp[cnt3] * 3 {
cnt3 ++
}
if dp[i] == dp[cnt5] * 5 {
cnt5 ++
}
}
return dp[n]
}LCR 185. 统计结果概率 - 力扣（LeetCode）
对于一个骰子的点数，有6种可能
dp[i][j]表示i个骰子且点数为j的次数，然后除以总次数来算概率
func statisticsProbability(num int) []float64 {
dp := make([][]int,num + 2)
for i := 0; i < num + 2; i ++ {
dp[i] = make([]int,num*6+1)
}
for i := 1; i <= 6; i ++ {
dp[1][i] = 1
}
for i := 2; i <= num; i ++ {
for j := i; j <= 6*i; j ++ {
//枚举这次点数是多少
for k := 1; k <= 6; k ++ {
if j - k >= 0 {
dp[i][j] = dp[i][j] + dp[i-1][j-k]
}
}
}
}
var ans []float64
var sum=1
for i := 1; i <= num ;i ++ {
sum *= 6
}
for i := num; i <= 6 * num; i ++ {
ans = append(ans, float64(dp[num][i])/float64(sum) )
}
return ans;
}评论 (0)
