灰子学算法之初级动态规划
算法:
本篇是动态规划的第一篇文章,对于动态规划的题目,其实就是数学中的归纳法,最终需要找到一个公式,找到后面的值与前面数据之间的关联关系。
对于本次的几个题目来讲,公式比较简单: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] }
执行结果:
算法: 本篇是动态规划的第一篇文章,对于动态规划的题目,其实就是数学中的归纳法,最终需要找到一个公式,找到后面的值与前面数据之间的关联关系。 对于本次的几个题目来讲,公式比较简单: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上一篇:
通过多线程提高代码的执行效率例子