算法:
本篇是动态规划的第一篇文章,对于动态规划的题目,其实就是数学中的归纳法,最终需要找到一个公式,找到后面的值与前面数据之间的关联关系。
对于本次的几个题目来讲,公式比较简单:f(n+2) = f(n)+f(n-1)+X,详细内容需要参见每道题目的分析。
题目1: https://leetcode-cn.com/problems/climbing-stairs/
代码实现:
/* 动态规划典型题目:
n=1, 只有1种走法
n=2, 有两种走法,1+1和2
n>2, 是n-1楼梯+1步和n-2楼梯+2步,这两种走法;走法是 f(n-1)+f(n-2)
*/
func climbStairs(n int) int {
if n < 2 {
return 1
}
res := make([]int,n)
res[0] = 1
res[1] = res[0]+1
for i:=2;i<n;i++ {
res[i] = res[i-1] + res[i-2]
}
return res[n-1]
}
执行结果:
题目2:
https://leetcode-cn.com/problems/min-cost-climbing-stairs/
代码实现:
// 公式:f(i) = f(i-1)+f(i-2)+cost[i]
func minCostClimbingStairs(cost []int) int {
l := len(cost)
if len(cost) < 2 {
return 0
}
res := make([]int,l)
// 0,1都是走1的的权重
res[0] = cost[0]
res[1] = cost[1]
// 2以上的话,是n-1,n-2 最小值+最后一个位置的cost
for i := 2; i< l; i++ {
// 动态规划的公式
res[i] = cost[i]+min(res[i-1],res[i-2])
}
return min(res[l-1],res[l-2])
}
func min(a,b int) int {
if a>b {
return b
}
return a
}
执行结果:
题目3:
https://leetcode-cn.com/problems/n-th-tribonacci-number/
代码实现:
// 公式:res[i]= res[i-1]+res[i-2]+res[i-3]
func tribonacci(n int) int {
if n == 0 {
return 0
}
if n ==1 || n==2{
return 1
}
res := make([]int,n+1)
res[0] = 0
res[1] = 1
res[2] = 1
for i:=3;i<=n;i++ {
res[i]= res[i-1]+res[i-2]+res[i-3]
}
return res[n]
}
执行结果: