【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] = 0int 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;
}