题解 | #矩形覆盖#

//本题用动态规划求解
//数学归纳法找规律 发现为斐波那契数列 f（n） = f（n-1） + f（n- 2）！（关键）
//以此建立状态转移方程求解

import java.util.*;
public class Solution {

    public int rectCover(int target) {

        if (target <= 2){
            return target;
        }
        int dp1 = 1;
        int dp2 = 2;
        int ans = 0;
        for (int i = 3; i <= target; i++) {
            ans = dp1 + dp2;
            dp1 = dp2;
            dp2 = ans;
        }
        return ans;
    }
}