6.动态规划

/*
动态规划
    动态规划和其它遍历算法（如深/广度优先搜索）都是将原问题拆成多个子问题然后求解，他们之间的最本质区别是，动态规划保存子问题的解，避免重复计算。
解决动态规划问题的关键是找到状态转移方程，这样我们可以通过计算和存储子问题的解来求解最终问题。

状态转移矩阵及dp数组初始化
*/


//70.爬楼梯
/*
题目描述：给定n节台阶，每次可以走一步或两步，求一共有多少种方式可以走完这些台阶。
输入输出样例：输入是一个数字，表示台阶数量；输出是爬台阶的总方式。
Input:3  Output:3
在这个样例中，一共有三种方法走完这三节台阶；每次走一步；先走一步，再走两步；先走两步，再走一步。
题解：这是十分经典的斐波那契数列问题。定义一个数组dp，dp[i]表示走到第i阶的方法数。因为我们每次可以走一步或者两步，所以第i阶台阶可以从第i-1或i-2阶
到达。换句话说，走到第i阶的方法数即为走到第i-1阶的方法数加上走到第i-2阶的方法数。这样我们就得到了状态转移方程dp[i]=dp[i-1]+dp[i-2]。注意边界条件
的处理。
*/
int climbStairs(int n){
    if(n<2) return n;
    vector<int> dp(n+1, 1);
    for(int i=2; i<=n; i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[n];
}


//198.打家劫舍
/*
题目描述：假如你是一个劫匪，并且决定抢劫一条街上的房子，每个房子内的钱财数量各不相同。如果你抢了两栋相邻的房子，则会触发警报机关。求在不触发机关的情况下
最多可以抢劫多少钱。
输入输出样例：输入是一个一维数组，表示每个房子的钱财数量；输出是劫匪可以最多抢劫的钱财数量。
Input:[2,7,9,3,1]  Output:12   在这个样例中，最多的抢劫方式为抢劫第1、3、5个房子
题解：定义一个数组dp,dp[i]表示抢劫到第i个房子时，可以抢劫的最大数量。我们考虑dp[i],此时可以抢劫的最大数量有两种可能，一种是我们选择不抢劫这个房子，此时
累计的金额即为dp[i-1];另一种是我们选择抢劫这个房子，那么此前累计的最大金额只能是dp[i-2],因为我们不能够抢劫第i-1个房子，那么此前累计的最大金额只能是dp[i-2],
因为我们不能够抢劫第i-1个房子，否则会触发警报机关。因此本题的状态转移方程为dp[i]=max(dp[i-1],nums[i-1]+dp[i-2]).
*/
int rob(vector<int>& nums){
    if(nums.empty()) return 0;
    int n=nums.size();
    vector<int> dp(n+1, 0);
    dp[1]=nums[0];
    for(int i=2; i<=n; i++){
        dp[i] = max(dp[i-1], nums[i-1]+dp[i-2]);
    }
    return dp[n];
}


//64.最小路径和
/*
题目描述：给定一个m*n大小的非负整数矩阵，求从左上角开始到右下角结束的、经过的数字的和最小的路径。每次只能向右或者向下移动。
输入输出样例：输入是一个二维数组，输出是最优路径的数字和。
Input:
[[1,3,1]
 [1,5,1]
 [4,2,1]]
Output:7
在这个样例中最优的路径为1->3->1->1->1.
题解：我们可以定义一个同样是二维的dp数组，其中dp[i][j]表示从左上角开始到(i,j)位置的最优路径的数字和。因为每次只能向下或者向右移动，我们可以很快容易得到
状态转移方程dp[i][j]=min(dp[i-1][j], dp[i][j-1])+grid[i][j],其中grid表示原数组。
*/
int minPathSum(vector<vector<int>>& grid){
    int m=grid.size(), n=grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(i==0 && j==0){
                dp[i][j]=gird[i][j];
            }else if(i==0){
                dp[i][j]=dp[i][j-1]+grid[i][j];
            }else if(j==0){
                dp[i][j]=dp[i-1][j]+grid[i][j];
            }else{
                dp[i][j]=min(dp[i-1][j], dp[i][j-1])+gird[i][j];
            }
        }
    }
    return dp[m-1][n-1];
}


//221.最大正方形
/*
题目描述：给定一个二维数组的0-1矩阵，求劝由1构成的最大正方形面积。
输入输出样例：输入是一个二维0-1数组，输出是最大正方形面积。
Input:
[[1,0,1,0,0]
 [1,0,1,1,1]
 [1,1,1,1,1]
 [1,0,0,1,0]]
Output:4
题解：对于在矩阵中搜索正方形或长方形的题型，一种常见的做法是定义一个二维dp数组，其中dp[i][j]表示满足题目条件的、以（i，j）为右下角的正方形
或者长方形的属性。对于本题，则表示以（i，j）为右下角的全由1构成的最大正方形面积。如果当前位置（matrix中）是0，那么dp[i][j]即为0；如果当前
位置是1，那么dp[i][j]为相邻的左、右、左上三个点的最小值+1，那么状态转移方程为dp[i][j]=min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))+1
*/
int maximalSquare(vector<vector<char>>& matrix){
    if(matrix.empty() || matrix[0].empty()){
        return 0;
    }
    int m = matrix.size(), n=matrix[0].size(), max_side = 0;
    vector<vector<int>> dp(m, vector<int>(n, 0));
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(matrix[i][j] = ‘1‘){                 //如果是0，dp[i][j]就直接是0
                if(i==0 || j==0){
                    dp[i][j]=1;          //dp数组第一行初始化
                }else{
                    dp[i][j]=min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))+1;
                }
            }
            max_side=max(max_side, dp[i][j]);
        }
    }
    return max_side*max_side;
}