1.给定一个字符串，找出其最长回文子串

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
}

也可以中心扩散，遍历字符串，判断第i，i为中心和第i, i+1为中心是否回文并判断最大值

2.给定一个数组，求出最大和的连续子数组

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]
}

变种：给定一个二维数组，求出从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级台阶，一次可以走1阶或2阶，一共有多少种方法到达n台阶

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.给定一个二维数组三角，求到达从顶到底的最短路径

[
[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.给定一个单词字典数组以及一个字符串，求字符串是否能由字典中的单词组成。

dp[i]为前i个字符是否满足要求

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.给定一个数组，元素有正有负，求出一个乘积最大的连续子序列

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.在一个由 0 和 1 组成的二维矩阵内，找到只包含 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.给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n,找出组合个数最小的个数

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.给定一个数组，求数组的单调递增的最长序列

dp[i]为以i为结尾的最长递增子序列

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
}