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 := 0for 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] =1dp[2] = 2for 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
//著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。