Problem: "Climbing Stairs with Costs" You are given a staircase with n steps, and you can either climb 1 or 2 steps at a time. Each step has a cost associated with it, given in an array cost[], where cost[i] represents the cost of the ith step. Your goal is to reach the top of the staircase in a way that minimizes the total cost. a.) What recurrence describes the optimal solution? b.) Prove the problem has an optimal substructure.

Problem: "Climbing Stairs with Costs" You are given a staircase with n steps, and you can either climb 1 or 2 steps at a time. Each step has a cost associated with it, given in an array cost[], where cost[i] represents the cost of the ith step. Your goal is to reach the top of the staircase in a way that minimizes the total cost. a.) What recurrence describes the optimal solution? b.) Prove the problem has an optimal substructure.