面試題47. 禮物的最大價(jià)值

概述：在一個(gè) m*n 的棋盤的每一格都放有一個(gè)禮物，每個(gè)禮物都有一定的價(jià)值（價(jià)值大于 0）。從棋盤的左上角開始拿格子里的禮物，并每次向右或者向下移動(dòng)一格、直到到達(dá)棋盤的右下角。給定棋盤及其上面的禮物的價(jià)值，求最大價(jià)值。
思路：剛開始爆搜去了，果斷給我T了，把數(shù)據(jù)緩存下來(lái)就a了，

int row,col;
    int map1[201][201];
    int maxValue(vector<vector<int>>& grid) {
     row=grid.size();
     if(!row) return 0;
     col=grid[0].size();
      return dfs(0,0,grid);
    }
    int dfs(int x,int y,vector<vector<int>>& grid){
        if(x>=row||y>=col) return 0;
        if(map1[x][y]>0) return map1[x][y];
        int a=dfs(x+1,y,grid),b=dfs(x,y+1,grid);
         map1[x][y]=grid[x][y]+max(a,b);
         return map1[x][y];
    }

打開題解一看，都是dp，，，
這是二維dp，用一個(gè)二維數(shù)組保存狀態(tài)，dp方程dp[i][j]=max(dp[i-1][j],dp[i][j-1])+grid[i][j]
初始條件是0行0列的值，因?yàn)樗峭彝屡艿摹?/p>

    int row,col;
    int map1[201][201];
    int maxValue(vector<vector<int>>& grid) {
     row=grid.size();  if(!row) return 0;
     col=grid[0].size();
     int dp[201][201];
     dp[0][0]=grid[0][0];
     for(int i=1;i<col;i++) dp[0][i]=dp[0][i-1]+grid[0][i];
     for(int i=1;i<row;i++)  dp[i][0]=dp[i-1][0]+grid[i][0];
     for(int i=1;i<row;i++)
         for(int j=1;j<col;j++)
             dp[i][j]=max(dp[i-1][j],dp[i][j-1])+grid[i][j];
     return dp[row-1][col-1];
    }

可以優(yōu)化成一維的

    int dp[201];
    int maxValue(vector<vector<int>>& grid) {
       int row=grid.size();
       int col=grid[0].size();
       for(int i=0;i<row;i++)
           for(int j=0;j<col;j++)
               dp[j+1]=max(dp[j],dp[j+1])+grid[i][j];
      return dp[col];
    }

264. 丑數(shù) II

概述：按順序找出前1670個(gè)丑數(shù)，丑數(shù)就是只包含質(zhì)因數(shù) 2, 3, 5 的正整數(shù)。
思路：這道題因?yàn)橄乱粋€(gè)丑數(shù)可由之前丑數(shù)計(jì)算出來(lái)，當(dāng)前狀態(tài)由之前狀態(tài)得出，滿足無(wú)后效性，也算是dp。
采用三指針做法，計(jì)算丑數(shù)時(shí)是選取三個(gè)里最小的那一個(gè)，然后將這個(gè)指針后移一位。

   int nthUglyNumber(int n) {
       double res[1693];
        int p2=0,p3=0,p5=0;
        res[0]=1;
     for(int i=1;i<1691;i++){
          res[i]=min(2*res[p2],min(3*res[p3],5*res[p5]));
          if(res[i]==2*res[p2]) p2++;
          if(res[i]==3*res[p3]) p3++;
          if(res[i]==5*res[p5]) p5++;
     }
     return (int)res[n-1];
    }

338. 比特位計(jì)數(shù)

概述：0-num中每一個(gè)數(shù)字的二進(jìn)制表示1的個(gè)數(shù)，O(n)的復(fù)雜度
思路：動(dòng)態(tài)規(guī)劃的思想，當(dāng)num為奇數(shù)時(shí)候，num-1是偶數(shù)，1的個(gè)數(shù)就是num-1中1的個(gè)數(shù)加1，
當(dāng)num為偶數(shù)時(shí)候，num-1為奇數(shù)，num不過(guò)是 num/2左移一位（可以理解為末尾加了個(gè)0），而1的個(gè)數(shù)沒(méi)有發(fā)生改變。

    vector<int> countBits(int num) {
        vector<int>res;
        /*for(int i=0;i<=num;i++){ //我的暴力代碼  果斷tttt
            int cnt=0;
            while(i){
                if(i&1==1) cnt++;
                i>>1;
            }
            res.push_back(cnt);
        }
        */
        res.push_back(0);
         for(int i=1;i<=num;i++){
             int cnt=0;;
             if(i&1) cnt=res[i-1]+1;
              else cnt=res[i/2];
              res.push_back(cnt);
         }
/*
      int[] ans = new int[num + 1]; //官方題解里的最低有效位的方法，比我的寫起來(lái)更簡(jiǎn)潔一些，
      for (int i = 1; i <= num; ++i)
        ans[i] = ans[i >> 1] + (i & 1);
*/
        return res; 
    }