JZ70 矩形覆盖

JZ70 矩形覆盖

矩形覆盖_牛客题霸_牛客网 (nowcoder.com)

---

// //递归
// import java.util.*;
// 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);
//     }
// }


//动规
import java.util.*;
public class Solution {
    public int rectCover(int target) {
        if(target==0) return 0;
        if(target==1) return 1;
        if(target==2) return 2;
        int[] dp=new int[target+1];
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=target;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[target];
    }
}