1.給定一個(gè)字符串，找出其最長(zhǎng)回文子串

dp[i][j]為字符串i-j位置是否回文

func longestPalindrome(s string) string {
    if len(s) < 2 {
        return s
    }
    dp := [][]bool{}
    maxLength := 1
    res := string(s[0])
    for i :=0; i < len(s); i ++ {
        dp = append(dp, make([]bool, len(s)))
        dp[i][i] = true
    }
    for i := 0; i < len(s); i ++ {
        for j := 0; j < i; j ++ {
            if s[i] == s[j] {
                if i - j <=2 {
                    dp[j][i] = true
                } else {
                    dp[j][i] = dp[j + 1][i - 1]
                }
            } else {
                dp[j][i] = false
            }
            if dp[j][i] && i - j + 1 > maxLength{
                maxLength = i - j + 1
                res = s[j: i + 1]
            }
        }
    }
    return res
}

也可以中心擴(kuò)散，遍歷字符串，判斷第i，i為中心和第i, i+1為中心是否回文并判斷最大值

2.給定一個(gè)數(shù)組，求出最大和的連續(xù)子數(shù)組

func maxSubArray(nums []int) int {
    dp := make([]int, len(nums))
    dp[0] = nums[0]
    max := dp[0]
    for i := 1; i < len(nums); i ++ {
        if dp[i - 1] < 0 {
            dp[i] = nums[i]
        } else {
            dp[i] = dp[i - 1] + nums[i]
        }
        if dp[i] > max {
            max = dp[i]
        }
    }
    return max
}

3.從dp[0[0]到dp[m-1][n-1]的所有路徑

func uniquePaths(m int, n int) int {
    dp := [][]int{}
    for i := 0; i < m; i ++ {
        dp = append(dp, make([]int, n))
    }
    for i := 0; i < n; i ++ {
        dp[0][i] = 1
    }
    for i := 0; i < m; i ++ {
        dp[i][0] = 1
    }
    for i := 1; i < m; i ++ {
        for j := 1; j < n; j ++ {
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    }
    return dp[m - 1][n - 1]
}

變種：中間有路障

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    dp := [][]int{}
     for i := 0; i < len(obstacleGrid); i ++ {
        dp = append(dp, make([]int, len(obstacleGrid[0])))
    }
    if obstacleGrid[0][0] == 1 {
        dp[0][0] = 0
    } else {
        dp[0][0] = 1
    }

    for i := 1; i < len(obstacleGrid[0]); i ++ {
        if obstacleGrid[0][i] == 1 {
            dp[0][i] = 0
        } else {
            dp[0][i] = dp[0][i - 1]
        }
    }
    for i := 1; i < len(obstacleGrid); i ++ {
        if obstacleGrid[i][0] == 1 {
            dp[i][0] = 0
        } else {
            dp[i][0] = dp[i - 1][0]
        }
    }
    for i := 1; i < len(obstacleGrid); i ++ {
        for j := 1; j < len(obstacleGrid[0]); j ++ {
            if obstacleGrid[i][j] == 1 {
                dp[i][j] = 0
            } else {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
            }
        }
    }
    return dp[len(obstacleGrid) - 1][len(obstacleGrid[0]) - 1]
}

變種：給定一個(gè)二維數(shù)組，求出從0,0到m-1， n-1的最短路徑

func minPathSum(grid [][]int) int {
    dp := [][]int{}
    for i := 0; i < len(grid); i ++ {
        dp = append(dp, make([]int, len(grid[0])))
    }
    dp[0][0] = grid[0][0]
    for i:= 1; i < len(grid[0]); i ++ {
        dp[0][i] = dp[0][i - 1] + grid[0][i]
    }
    for i:= 1; i < len(grid); i ++ {
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    }
    for i := 1; i < len(grid); i ++ {
        for j := 1; j < len(grid[0]); j ++ {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        }
    }
    return dp[len(grid) - 1][len(grid[0]) - 1]
}

4.一共n級(jí)臺(tái)階，一次可以走1階或2階，一共有多少種方法到達(dá)n臺(tái)階

func climbStairs(n int) int {
    if n < 2 {
        return 1
    } 
    dp := make([]int, n + 1)
    dp[0] = 1
    dp[1] = 1
    for i := 2; i <= n; i ++ {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

5.給定一個(gè)二維數(shù)組三角，求到達(dá)從頂?shù)降椎淖疃搪窂?/h3>

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]

func minimumTotal(triangle [][]int) int {
    dp := [][]int{}
    for i := 0; i < len(triangle); i ++ {
        dp = append(dp, make([]int, len(triangle[i])))
    }
    dp[0][0] = triangle[0][0]
    if len(triangle)< 2 {
        return dp[0][0]
    }
    for i := 1; i < len(triangle); i ++ {
        dp[i][0] = dp[i - 1][0] + triangle[i][0]
    }
    dp[1][1] = triangle[1][1] + dp[0][0]
    for i := 2; i < len(triangle); i ++ {
        for j := 1; j < len(triangle[i]); j ++ {
            if j == len(triangle[i]) - 1 {
                dp[i][j] = dp[i - 1][j - 1] + triangle[i][j]
            } else {
                dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j]
            }
        }
    }
    res := dp[len(triangle) - 1][0]
    for i := 1; i < len(triangle[len(triangle) - 1]); i ++ {
        res = min(res, dp[len(triangle) - 1][i])
    }
    return res
}

6.給定一個(gè)單詞字典數(shù)組以及一個(gè)字符串，求字符串是否能由字典中的單詞組成。

dp[i]為前i個(gè)字符是否滿足要求

func wordBreak(s string, wordDict []string) bool {
    set := make(map[string]int, len(wordDict))
    for _, value := range(wordDict) {
        set[value] = 1
    }
    dp := make([]bool, len(s) + 1)
    dp[0] = true
    for i := 0; i < len(s); i ++ {
        for j:= i + 1; j <= len(s); j++ {
            if _, ok := set[s[i:j]]; ok && dp[i] {
                dp[j] = true
            }
        }
    }
    return dp[len(s)]
}

7.給定一個(gè)數(shù)組，元素有正有負(fù)，求出一個(gè)乘積最大的連續(xù)子序列

func maxProduct(nums []int) int {
    dpMin := make([]int, len(nums))
    dpMin[0] = nums[0]
    dpMax := make([]int, len(nums))
    dpMax[0] = nums[0]
    max := nums[0]
    for i := 1; i < len(nums); i ++ {
        dpMax[i] = maxFind(dpMax[i-1] * nums[i], maxFind(dpMin[i-1]*nums[i], nums[i]))
        dpMin[i] = minFind(dpMin[i-1] * nums[i], minFind(dpMax[i-1]*nums[i], nums[i]))
        if dpMax[i] > max {
            max = dpMax[i]
        }
    }
    return max
}

8.在一個(gè)由 0 和 1 組成的二維矩陣內(nèi)，找到只包含 1 的最大正方形,并返回其面積

func maximalSquare(matrix [][]byte) int {
    dp := make([][]int, len(matrix))
    for i := 0; i < len(matrix); i ++ {
        dp[i] = make([]int, len(matrix[0]))
    }
    res := 0
    for i := 0; i < len(matrix); i ++ {
        for j := 0; j < len(matrix[0]); j ++ {
            if matrix[i][j] == '1' {
                if i == 0 || j == 0 {
                    dp[i][j] = 1
                    res = max(dp[i][j], res)
                } else {
                    dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1
                    res = max(dp[i][j], res)
                }

            } else {
                dp[i][j] = 0
            }
        }
    }
    return res * res
}

9.給定正整數(shù) n，找到若干個(gè)完全平方數(shù)（比如 1, 4, 9, 16, ...）使得它們的和等于 n,找出組合個(gè)數(shù)最小的個(gè)數(shù)

func numSquares(n int) int {
    dp := make([]int, n + 1)
    dp[0] = 0
    for i := 1; i <= n; i ++ {
        dp[i] = i
        for j := 1; i - j * j >= 0; j ++ {
            dp[i] = min(dp[i], dp[i - j * j] + 1)
        }
    }
    return dp[n]
}

10.給定一個(gè)數(shù)組，求數(shù)組的單調(diào)遞增的最長(zhǎng)序列

dp[i]為以i為結(jié)尾的最長(zhǎng)遞增子序列

func lengthOfLIS(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    dp := make([]int, len(nums))
    res := 1
    for i := 0; i < len(nums); i ++ {
        dp[i] = 1
        for j := 0; j < i; j ++ {
            if nums[j] < nums[i] {
                dp[i] = max(dp[j] + 1, dp[i])
            }
        }
        res = max(res, dp[i])
    }
    return res
}