LeetCode75学习计划-动态规划

算法解题思路很多会借鉴于题解区，如果侵权请联系删除。

本章节知识点为动态规划。

第N个斐波那契数

题目标签：

• 动态规划

题目难度： Easy

题目描述：

泰波那契序列 Tn 定义如下：

``T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0的条件下Tn+3 = Tn + Tn+1 + Tn+2`

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

解题思路：

• 动态规划方式解

代码实现：

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

使用最小花费爬楼梯

题目标签：

• 动态规划

题目难度： Easy

题目描述：

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

解题思路：

• 动态规划方式解

代码实现：

func minCostClimbingStairs(cost []int) int {
  n := len(cost)
  dp := make([]int, n+1)
  dp[0] = 0
  dp[1] = 0
  for i := 2; i<=n;i++ {
    dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
  }
  return dp[n]
}
func min(a, b int) int {
  if a < b {
    return a
  }
  return b
}

打家劫舍

题目标签：

• 动态规划
• 数组

题目难度： Medium

题目描述：

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

解题思路：

• 动态规划方式解

代码实现：

func rob(nums []int) int {
  n := len(nums)
  if n == 1 {
    return nums[0]
  }
  if n == 2 {
    return max(nums[0], nums[1])
  }
  dp := make([]int, n)
  dp[0] = nums[0]
  dp[1] = max(nums[0], nums[1])
  for i := 2; i < n; i++ {
    // 不偷当前的 / 偷当前的
    dp[i] = max(dp[i-1], dp[i-2] + nums[i])
  }
  return dp[n-1]
}
func max(a, b int) int {
  if a > b {
    return a
  }
  return b
}

不同路径

题目标签：

• 动态规划
• 多维数组

题目难度： Medium

题目描述：

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

解题思路：

• 动态规划方式解

代码实现：

func uniquePaths(m int, n int) int {
  // 二维数组
  dp := make([][]int, m)
  // 初始值
  for i := range dp {
    dp[i] = make([]int, n)
    dp[i][0] = 1 
  }
  for j := 0; j < n; j++ {
    dp[0][j] = 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]
}

最长公共子序列

题目标签：

• 动态规划
• 多维数组

题目难度： Medium

题目描述：

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

解题思路：

• 二维动态规划求解

代码实现：

func longestCommonSubsequence(text1 string, text2 string) int {
  m := len(text1)
  n := len(text2)
  // 初始化dp
  dp := make([][]int, m+1)
  for i := range dp {
    dp[i] = make([]int, n+1)
  }
  for i, c1 := range text1 {
    for j, c2 := range text2 {
      if c1 == c2 {
        dp[i+1][j+1] = dp[i][j] + 1
      } else {
        dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
      }
    }
  }
  return dp[m][n]
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}