题解 | #矩形覆盖#

public class Solution {
    /*方式一：递归*/
    public int rectCover(int target) {
        if(target == 0) return 0;
        if(target == 1) return 1;
        if(target == 2) return 2;
        return rectCover(target-1)+rectCover(target-2);
    }

    /*方式二：动态规划思想--dp存值*/
    public int rectCover2(int target) {
        if(target == 0) return 0;
        if(target == 1) return 1;
        if(target == 2) return 2;
        int[] dp = new int[target + 1];
        dp[1]=1;
        dp[2]=2;
        for (int i = 3; i <= target; i++) {
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[target];
    }

    /*方式三：动态规划思想--存结果值*/
    public int rectCover3(int target) {
        if(target == 0) return 0;
        if(target == 1) return 1;
        if(target == 2) return 2;
        int num1=1;
        int num2=2;
        int result = 0;
        for (int i = 3; i <=target; i++) {
            result = num1+num2;
            num1 = num2;
            num2 = result;
        }
        return result;
    }
}

解题思想：递归（找规律）或者动态规划（数组存值或者结果赋值）