经典动态规划入门
看难题看累了找个简单的换换脑子。
爬楼梯,每次爬1或2层,问爬到第n层有几种方法。
class Solution { public: int climbStairs(int n) { if(n<3) return n; int ans=0; int f1,f2; f1=1;f2=2; for(int i=3;i<=n;i++) { ans=f1+f2; f1=f2;f2=ans; } return ans; } };
动态规划后就成了斐波那契数列,直接算即可。
经典动态规划入门
看难题看累了找个简单的换换脑子。
爬楼梯,每次爬1或2层,问爬到第n层有几种方法。
class Solution { public: int climbStairs(int n) { if(n<3) return n; int ans=0; int f1,f2; f1=1;f2=2; for(int i=3;i<=n;i++) { ans=f1+f2; f1=f2;f2=ans; } return ans; } };
动态规划后就成了斐波那契数列,直接算即可。