DAY41

動態規劃理論基礎

還差閆氏分析法沒學完。見B站收藏夾。

前兩題學習初始化方式就好vector<int> dp(N+1);

509斐波那契數

簡單。

1. class?Solution?{
2. public:
3. ????int?fib(int?N)?{
4. ????????if?(N?<=?1)?return?N;
5. ????????int?dp[2];
6. ????????dp[0]?=?0;
7. ????????dp[1]?=?1;
8. ????????for?(int?i?=?2;?i?<=?N;?i++)?{
9. ????????????int?sum?=?dp[0]?+?dp[1];
10. ????????????dp[0]?=?dp[1];
11. ????????????dp[1]?=?sum;
12. ????????}
13. ????????return?dp[1];
14. ????}
15. };

70爬樓梯

簡單。

1. class?Solution?{
2. public:
3. ????int?climbStairs(int?n)?{
4. ????????if?(n?<=?1)?return?n;
5. ????????int?dp[3];
6. ????????dp[1]?=?1;
7. ????????dp[2]?=?2;
8. ????????for?(int?i?=?3;?i?<=?n;?i++)?{
9. ????????????int?sum?=?dp[1]?+?dp[2];
10. ????????????dp[1]?=?dp[2];
11. ????????????dp[2]?=?sum;
12. ????????}
13. ????????return?dp[2];
14. ????}
15. };

746使用最小花費爬樓梯

不會做了，實在想不出來。

代碼隨想錄官方解答：

現在會了。主要是狀態轉移的形式，學一下：

1. class?Solution?{
2. public:
3. ????int?minCostClimbingStairs(vector<int>&?cost)?{
4. ????if(cost.size()==2)?return?min(cost[0],cost[1]);
5. ????vector<int>?dp(cost.size()+1);
6. ????dp[0]=0,dp[1]=0;
7. ????for(int?i=2;i<dp.size();i++){
8. ????????dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
9. ????}
10. ????return?dp[dp.size()-1];
11. ????}
12. };

54螺旋矩陣

廈大保研夏令營考過，練一練。

終于過了，卡在記錄該位置是否已經走過，用unordered_set, unordered_map顯然都不行。想復雜了，用二維數組bool就好了。

1. ????class?Solution?{
2. ????public:
3. ????????vector<int>?spiralOrder(vector<vector<int>>&?matrix)?{
4. ????????????vector<int>?res;
5. ????????????int?dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
6. ????????????vector<vector<bool>>?flag(matrix.size(),vector<bool>(matrix[0].size(),false));
7. ????????????int?size=matrix.size()*matrix[0].size();
8. ????????????for(int?x=0,y=0,d=0,k=1;k<=size;k++){
9. ????????????????flag[x][y]=true;
10. ????????????????res.push_back(matrix[x][y]);
11. ????????????????int?a=x+dx[d],b=y+dy[d];
12. ????????????????if(a<0||a>=matrix.size()||b<0||b>=matrix[0].size()||flag[a][b]){
13. ????????????????????d=(d+1)%4;
14. ????????????????????a=x+dx[d],b=y+dy[d];
15. ????????????????}
16. ????????????????x=a,y=b;
17. ????????????}
18. ????????????return?res;
19. ????????}
20. ????};

59螺旋矩陣ii

廈大保研夏令營考過，練一練。ACWING語法基礎課做過，再寫一遍：

還是寫不出來，不知道該怎么利用偏移量去更新。

加油吧：

1. class?Solution?{
2. public:
3. ????vector<vector<int>>?generateMatrix(int?n)?{
4. ????int?dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
5. ????vector<vector<int>>?res(n,vector<int>(n,0));
6. ????int?mi=n*n;
7. ????for(int?x=0,y=0,d=0,k=1;k<=mi;k++){
8. ????????res[x][y]=k;
9. ????????int?a=x+dx[d],b=y+dy[d];
10. ????????//撞墻或者走過了,不要漏了“走過”
11. ????????if(a<0||a>n-1||b<0||b>n-1||res[a][b]){
12. ????????????d=(d+1)%4;
13. ????????????a=x+dx[d],b=y+dy[d];
14. ????????}
15. ????????x=a,y=b;
16. ????}
17. ????return?res;
18. ????}
19. };