3693. Climbing Stairs II Medium

1/**
2 * [3693] Climbing Stairs II
3 *
4 * You are climbing a staircase with n + 1 steps, numbered from 0 to n.
5 * You are also given a 1-indexed integer array costs of length n, where costs[i] is the cost of step i.
6 * From step i, you can jump only to step i + 1, i + 2, or i + 3. The cost of jumping from step i to step j is defined as: costs[j] + (j - i)^2
7 * You start from step 0 with cost = 0.
8 * Return the minimum total cost to reach step n.
9 *  
10 * <strong class="example">Example 1:
11 * <div class="example-block">
12 * Input: <span class="example-io">n = 4, costs = [1,2,3,4]</span>
13 * Output: <span class="example-io">13</span>
14 * Explanation:
15 * One optimal path is 0 &rarr; 1 &rarr; 2 &rarr; 4
16 * <table style="border: 1px solid black;">
17 * 	<tbody>
18 * 		<tr>
19 * 			<th style="border: 1px solid black;">Jump</th>
20 * 			<th style="border: 1px solid black;">Cost Calculation</th>
21 * 			<th style="border: 1px solid black;">Cost</th>
22 * 		</tr>
23 * 	</tbody>
24 * 	<tbody>
25 * 		<tr>
26 * 			<td style="border: 1px solid black;">0 &rarr; 1</td>
27 * 			<td style="border: 1px solid black;">costs[1] + (1 - 0)^2 = 1 + 1</td>
28 * 			<td style="border: 1px solid black;">2</td>
29 * 		</tr>
30 * 		<tr>
31 * 			<td style="border: 1px solid black;">1 &rarr; 2</td>
32 * 			<td style="border: 1px solid black;">costs[2] + (2 - 1)^2 = 2 + 1</td>
33 * 			<td style="border: 1px solid black;">3</td>
34 * 		</tr>
35 * 		<tr>
36 * 			<td style="border: 1px solid black;">2 &rarr; 4</td>
37 * 			<td style="border: 1px solid black;">costs[4] + (4 - 2)^2 = 4 + 4</td>
38 * 			<td style="border: 1px solid black;">8</td>
39 * 		</tr>
40 * 	</tbody>
41 * </table>
42 * Thus, the minimum total cost is 2 + 3 + 8 = 13
43 * </div>
44 * <strong class="example">Example 2:
45 * <div class="example-block">
46 * Input: <span class="example-io">n = 4, costs = [5,1,6,2]</span>
47 * Output: <span class="example-io">11</span>
48 * Explanation:
49 * One optimal path is 0 &rarr; 2 &rarr; 4
50 * <table style="border: 1px solid black;">
51 * 	<tbody>
52 * 		<tr>
53 * 			<th style="border: 1px solid black;">Jump</th>
54 * 			<th style="border: 1px solid black;">Cost Calculation</th>
55 * 			<th style="border: 1px solid black;">Cost</th>
56 * 		</tr>
57 * 	</tbody>
58 * 	<tbody>
59 * 		<tr>
60 * 			<td style="border: 1px solid black;">0 &rarr; 2</td>
61 * 			<td style="border: 1px solid black;">costs[2] + (2 - 0)^2 = 1 + 4</td>
62 * 			<td style="border: 1px solid black;">5</td>
63 * 		</tr>
64 * 		<tr>
65 * 			<td style="border: 1px solid black;">2 &rarr; 4</td>
66 * 			<td style="border: 1px solid black;">costs[4] + (4 - 2)^2 = 2 + 4</td>
67 * 			<td style="border: 1px solid black;">6</td>
68 * 		</tr>
69 * 	</tbody>
70 * </table>
71 * Thus, the minimum total cost is 5 + 6 = 11
72 * </div>
73 * <strong class="example">Example 3:
74 * <div class="example-block">
75 * Input: <span class="example-io">n = 3, costs = [9,8,3]</span>
76 * Output: <span class="example-io">12</span>
77 * Explanation:
78 * The optimal path is 0 &rarr; 3 with total cost = costs[3] + (3 - 0)^2 = 3 + 9 = 12
79 * </div>
80 *  
81 * Constraints:
82 * 
83 * 	1 <= n == costs.length <= 10^5​​​​​​​
84 * 	1 <= costs[i] <= 10^4
85 * 
86 */
87pub struct Solution {}
88
89// problem: https://leetcode.com/problems/climbing-stairs-ii/
90// discuss: https://leetcode.com/problems/climbing-stairs-ii/discuss/?currentPage=1&orderBy=most_votes&query=
91
92// submission codes start here
93
94impl Solution {
95    pub fn climb_stairs(n: i32, costs: Vec<i32>) -> i32 {
96        0
97    }
98}
99
100// submission codes end
101
102#[cfg(test)]
103mod tests {
104    use super::*;
105
106    #[test]
107    fn test_3693() {
108    }
109}
110