共计 2712 个字符，预计需要花费 7 分钟才能阅读完成。
package dynamic
// 比如说输出 nums=[10,9,2,5,3,7,101,18]，其中最长的递增子序列是 [2,3,7,101]，所以算法的输入应该是 4。
func lengthOfLIS(nums []int) int {
m := len(nums)
dp := make([]int, m)
res := 0
for i := 0; i < m; i++ {dp[i] = 1
}
for i := 0; i < m; i++ {
for j := 0; j < i; j++ {if nums[i] > nums[j] {dp[i] = max(dp[i], dp[j] + 1)
}
res = max(res, dp[i])
}
}
return res}
func max(args …int) int {
res := args[0]
for _, v := range args {
if v > res {res = v}
}
return res}
// 比如说输出 nums = [-3,1,3,-1,2,-4,2]，算法返回 5，因为最大子数组 [1,3,-1,2] 的和为 5。
func maxSubArray(nums []int) int {
if len(nums) <=0 {return 0}
m := len(nums)
dp := make([]int, m)
dp[0] = nums[0]
res := nums[0]
for i:=1; i<m; i++ {dp[i] = max(nums[i], dp[i-1] + nums[i])
res = max(res, dp[i])
}
return res}
func qianzhuihe(nums []int, k int) int {
ret :=[][]int{}
for i:=0; i <len(nums); i++ {
sum :=0
res :=[]int{}
for j:=i; j<len(nums); j++ {sum +=nums[j]
res = append(res, nums[j])
if sum > k {break}
if sum == k {ret = append(ret, res)
}
}
}
return len(ret)}
// 假如你正在爬楼梯。须要 n 阶你能力达到楼顶。
//
// 每次你能够爬 1 或 2 个台阶。你有多少种不同的办法能够爬到楼顶呢
// 示例 1：
//
// 输出：n = 2
// 输入：2
// 解释：有两种办法能够爬到楼顶。
//1. 1 阶 + 1 阶
//2. 2 阶
// 示例 2：
//
// 输出：n = 3
// 输入：3
// 解释：有三种办法能够爬到楼顶。
//1. 1 阶 + 1 阶 + 1 阶
//2. 1 阶 + 2 阶
//3. 2 阶 + 1 阶
//
func climbStairs(n int) int {
if n <=2 {return n}
dp :=make([]int, n+1)
dp[1] =1
dp[2] = 2
for i:=3; i<=n; i++ {dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]}
// 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
//
// 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
// 输出: numRows = 5
// 输入: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
// 示例 2:
//
// 输出: numRows = 1
// 输入: [[1]]
// dpi = dpi-1 + dpi-1
func generate(numRows int) [][]int{
dp := make([][]int, numRows)
for i:=0; i < numRows; i++ {dp[i] = make([]int, i+1)
dp[i][0] = 1
dp[i][i] = 1
}
for i:=2; i < numRows; i++ {
for j:=1; j < i; j ++ {dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
}
}
return dp}
func editDistance(word1, word2 string) int {
if len(word1) == 0 {return len(word2)
}
if len(word2) == 0 {return len(word1)
}
m := len(word1)
n := len(word2)
dp := make([][]int, m+1)
for i :=0; i<=m; i++ {dp[i] = make([]int, n+1)
}
for i:=1; i<=m; i++{dp[i][0] = i
}
for j:=1; j<=n;j++ {dp[0][j] = j
}
for i:=1; i<=m;i++ {
for j:=1; j<=n;j++ {if word1[i-1] == word2[j-1] {dp[i][j] = dp[i-1][j-1]
} else {dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
}
}
}
return dp[m][n]}
func longestCommonSubsequence(text1 string, text2 string) int {
if len(text1) == 0 {return 0}
if len(text2) == 0 {return 0}
m, n := len(text1), len(text2)
dp := make([][]int, m+1)
for i:=0; i <=m; i++ {dp[i] = make([]int, n+1)
}
for i:=1;i <=m; i++ {
for j:=1; j<=n; j++ {if text1[i-1] == text2[j-1] {dp[i][j] = dp[i-1][j-1] + 1
} else {dp[i][j] = max(dp[i-1][j], dp[i][j-1])
}
}
}
return dp[m][n]}
func min(arg …int) int {
min :=arg[0]
for _,v :=range arg {
if v <min {min = v}
}
return min}
// 给你一个整数数组 nums 和一个整数 target。
//
// 向数组中的每个整数前增加 ‘+’ 或 ‘-‘，而后串联起所有整数，能够结构一个 表达式：
//
// 例如，nums = [2, 1]，能够在 2 之前增加 ‘+’，在 1 之前增加 ‘-‘，而后串联起来失去表达式 “+2-1”。
// 返回能够通过上述办法结构的、运算后果等于 target 的不同 表达式 的数目。
//
//
//
// 示例 1：
//
// 输出：nums = [1,1,1,1,1], target = 3
// 输入：5
// 解释：一共有 5 种办法让最终目标和为 3。
//-1 + 1 + 1 + 1 + 1 = 3
//+1 – 1 + 1 + 1 + 1 = 3
//+1 + 1 – 1 + 1 + 1 = 3
//+1 + 1 + 1 – 1 + 1 = 3
//+1 + 1 + 1 + 1 – 1 = 3
//
//
// 起源：力扣（LeetCode）
// 链接：https://leetcode.cn/problems/target-sum
// 著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。
