hello-algo/codes/swift/chapter_dynamic_programming/climbing_stairs_constraint_dp.swift

37 lines
935 B
Swift
Raw Permalink Normal View History

/**
* File: climbing_stairs_constraint_dp.swift
* Created Time: 2023-07-15
* Author: nuomi1 (nuomi1@qq.com)
*/
/* */
func climbingStairsConstraintDP(n: Int) -> Int {
if n == 1 || n == 2 {
2023-08-31 02:31:58 +08:00
return 1
}
// dp
var dp = Array(repeating: Array(repeating: 0, count: 3), count: n + 1)
//
dp[1][1] = 1
dp[1][2] = 0
dp[2][1] = 0
dp[2][2] = 1
//
for i in 3 ... n {
dp[i][1] = dp[i - 1][2]
dp[i][2] = dp[i - 2][1] + dp[i - 2][2]
}
return dp[n][1] + dp[n][2]
}
@main
enum ClimbingStairsConstraintDP {
/* Driver Code */
static func main() {
let n = 9
let res = climbingStairsConstraintDP(n: n)
print("\(n) 阶楼梯共有 \(res) 种方案")
}
}