【LeetCode】动态规划--题目练习

有关动态规划算法的整理：添加链接描述

1.爬楼梯

70. 爬楼梯:LeetCode70

int climbStairs(int n) {
    //1.确定dp数组和意义 dp[n]表示第n阶的方法
    //2.确定递推关系式 dp[n] = dp[n-1]+dp[n-2];
    //3.初始化
    int dp[50] = {0};
    dp[1] = 1;
    dp[2] = 2;
    for(int i = 3;i<=n;i++){
        dp[i] = dp[i-1]+dp[i-2];
    }
    return dp[n];
}

2.第 N 个泰波那契数

1137.第 N 个泰波那契数:LeetCode1137

int tribonacci(int n){
    //1.确定dp数组和意义 dp[n]表示第n个数
    //2.确定递推关系式 dp[n] = dp[n-1]+dp[n-2]+dp[n-3];
    //3.初始化
    int dp[100] = {0};
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 1;
    for(int i = 3;i<=n;i++){
        dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
    }
    return dp[n];


}

3.使用最小花费爬楼梯

746.使用最小花费爬楼梯：LeetCode746

int minCostClimbingStairs(int* cost, int costSize) {
    //1.确定dp数组和意义 dp[n]表示第n台阶最小花费
    //2.确定递推关系式 dp[n] = min(dp[n-1]+cost[n-1],dp[n-2]+cost[n-2]);
    //3.初始化 dp[0] = 0;dp[1] = 0
    int dp[costSize + 1];
    dp[0] = dp[1] = 0;
    for (int i = 2; i <= costSize; i++) {
        dp[i] = fmin(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    }
    return dp[costSize];
}

4.打家劫舍

198.打家劫舍:LeetCode198

int rob(int* nums, int numsSize) {
    //1.确定dp数组和意义 dp[n]表示最大金额
    //2.确定递推关系式 dp[n] = max()
    //3.初始化 dp[0];dp[1] 
    //考虑特殊情况
    int dp[numsSize+1];
    dp[0] = nums[0];
    if(numsSize == 1){
        return nums[0];
    }
    //只有两家
    if(nums[1]<nums[0]){
        dp[1] = dp[0];
    }else{
        dp[1] = nums[1];
    }
    //dp[1] = nums[1];

    for(int i = 2;i<numsSize;i++){
        dp[i]=fmax(dp[i-2]+nums[i],dp[i-1]);
    }
    //dp[numsSize-1]=fmax(dp[numsSize-3]+nums[numsSize-1],dp[numsSize-2]);
    return dp[numsSize-1];

}

5.最小路径和

64.最小路径和:[LeetCode64]

int minPathSum(int** grid, int gridSize, int* gridColSize) {
    //向下 （i,j+1）向右(i+1,j)
    //1.确定dp数组和意义 dp[m-1][n-1]是最小的数字和
    //2.确定递推关系式 dp[m-1][n-1] = fmin(dp[m-1-1][n-1],dp[m-1][n-1-1])+grid[m-1][n-1];
    //向上寻找，向左寻找
    //3.初始化 dp[0][0] = grid[0][0];
    //考虑特殊情况
    int rows = gridSize, columns = gridColSize[0];
    if (rows == 0 || columns == 0) {
        return 0;
    }
    int dp[rows][columns];
    dp[0][0] = grid[0][0];
    for (int i = 1; i < rows; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    for (int j = 1; j < columns; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    for (int i = 1; i < rows; i++) {
        for (int j = 1; j < columns; j++) {
            dp[i][j] = fmin(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }
    return dp[rows - 1][columns - 1];
}

6.不同路径

62.不同路径:[LeetCode62]

int uniquePaths(int m, int n) {
    //向下 （i,j+1）向右(i+1,j)
    //1.确定dp数组和意义 dp[m-1][n-1]是最多的路径
    //2.确定递推关系式 dp[m-1][n-1] = dp[m-1-1][n-1]+dp[m-1][n-1-1];
    //向上寻找，向左寻找
    //3.初始化 dp[0][0] = 0
    //考虑特殊情况  只有一行 一列
    int dp[m][n];
    dp[0][0] = 0;
    if(m==1||n==1){
        return 1;
    }
    for(int i = 0;i<m;i++){
    	dp[i][0] = 1;
	}
	for(int j = 0;j<n;j++){
		dp[0][j] = 1;
	}
    dp[0][1]=1;
    dp[1][0]=1;
    for(int i = 1;i<m;i++){
        for(int j = 1;j<n;j++){
            dp[i][j] = dp[i-1][j]+dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

7.下降路径最小和

931.下降路径最小和:LeetCode931

int minFallingPathSum(int** matrix, int matrixSize, int* matrixColSize) {
    int n=matrixSize;//n*n
    //int n=matrixColSize[0];//列数
    //三个位置 [i+1][j+1];[i+1][j];[i+1][j-1]
    //1.确定dp数组和意义 dp[][]最后比较大小
    //2.确定递推关系式 dp[i][j] = fmin(fmin(dp[i-1][j],dp[i-1][j-1]),dp[i-1][j+1])+ma[i][j];
    //3.初始化 第一行 dp = ma[][];
    //考虑特殊情况
    int dp[110][110]={{0}};
    //初始化
    for(int i = 0;i<n;i++){
        dp[0][i]=matrix[0][i];
    }
    if(n==1){
        return matrix[0][0];
    }
    if(n==2){
        dp[1][1]=fmin(dp[0][1],dp[0][0])+matrix[1][1];
        dp[1][0]=fmin(dp[0][1],dp[0][0])+matrix[1][0];
        return fmin(dp[1][1],dp[1][0]);
    }
    for(int i = 1;i<n;i++){
        for(int j=0;j<n;j++){
            if(j+1>=n){//右边界列
                dp[i][n-1]=fmin(dp[i-1][n-1],dp[i-1][n-2])+matrix[i][n-1];
            }else if(j-1<0){//左边界列
                dp[i][0]=fmin(dp[i-1][0],dp[i-1][1])+matrix[i][0];
            }else{
            dp[i][j]=fmin(fmin(dp[i-1][j],dp[i-1][j-1]),dp[i-1][j+1])+matrix[i][j];
            } 
        }
    }
    int mm=99999;//求最后一行最小值
    for(int i = 1;i<n;i++){
        mm = fmin(fmin(dp[n - 1][i - 1], dp[n - 1][i]),mm);
    }
    return mm;
}