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; } }
解题思想:递归(找规律)或者动态规划(数组存值或者结果赋值)