面试题47. 礼物的最大价值

概述：在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定棋盘及其上面的礼物的价值，求最大价值。
思路：刚开始爆搜去了，果断给我T了，把数据缓存下来就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，用一个二维数组保存状态，dp方程dp[i][j]=max(dp[i-1][j],dp[i][j-1])+grid[i][j]
初始条件是0行0列的值，因为他是往右往下跑的。

    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];
    }

可以优化成一维的

    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. 丑数 II

概述：按顺序找出前1670个丑数，丑数就是只包含质因数 2, 3, 5 的正整数。
思路：这道题因为下一个丑数可由之前丑数计算出来，当前状态由之前状态得出，满足无后效性，也算是dp。
采用三指针做法，计算丑数时是选取三个里最小的那一个，然后将这个指针后移一位。

   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. 比特位计数

概述：0-num中每一个数字的二进制表示1的个数，O(n)的复杂度
思路：动态规划的思想，当num为奇数时候，num-1是偶数，1的个数就是num-1中1的个数加1，
当num为偶数时候，num-1为奇数，num不过是 num/2左移一位（可以理解为末尾加了个0），而1的个数没有发生改变。

    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]; //官方题解里的最低有效位的方法，比我的写起来更简洁一些，
      for (int i = 1; i <= num; ++i)
        ans[i] = ans[i >> 1] + (i & 1);
*/
        return res; 
    }