算法 - (动态规划)
动态规划 讲解动态规划的资料很多，官方的定义是指把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解。概念中的各阶段之间的关系，其实指的就是状态转移方程。很多人觉得DP难（下文统称动态规划为DP），根本原因是因为DP区别于一些固定形式的算法（比如DFS、二分法、KMP），没有实际的步骤规定第一步第二步来做什么，所以准确的说，DP其实是一种解决问题的思想。
动态规划的关键在于状态的定义，比如 opt[n] 、dp[n]、fib[n] 等。另外就是状态转移方程：opt[n] = best_of(opt[n-1], opt[n-2], …)
No.70 爬楼梯 链接：https://leetcode.cn/problems/climbing-stairs/ 思路：假设我当前爬到第 N 层，那么我多少种爬法？爬到第N层无非最后一次爬是有两种可能，最后一次爬2楼，最后一次爬1楼，最后一次爬两楼的话，就变成了 dp[n] = dp[n-2] , 最后一次爬一楼就变成了 dp[n] = dp[n-1] ,组合起来就是 dp[n] = dp[n-1] + dp[n-2] 为了从1开始计算到n，每层楼梯有多少种爬法，还需要一次循环
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 func climbStairs(n int) int { if n == 1 { return 1 } dp := make([]int, n+1) dp[1] = 1 // 一层楼梯1种爬法 dp[2] = 2 // 两层楼梯2种爬法，一次爬2层，爬2个一层 for i := 3; i <= n; i++ { dp[i] = dp[i-1] + dp[i-2] } return dp[n] } No.