免费网站建设那个好,整合营销网站建设,网页制作教程 基础,wordpress新闻动态插件有关动态规划算法的整理#xff1a;添加链接描述
1.爬楼梯
爬楼梯: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;in;i){dp[i] …有关动态规划算法的整理添加链接描述
1.爬楼梯
爬楼梯: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;in;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;in;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[numsSize1];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;inumsSize;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,j1向右(i1,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,j1向右(i1,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(m1||n1){return 1;}for(int i 0;im;i){dp[i][0] 1;}for(int j 0;jn;j){dp[0][j] 1;}dp[0][1]1;dp[1][0]1;for(int i 1;im;i){for(int j 1;jn;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 nmatrixSize;//n*n//int nmatrixColSize[0];//列数//三个位置 [i1][j1];[i1][j];[i1][j-1]//1.确定dp数组和意义 dp[][]最后比较大小//2.确定递推关系式 dp[i][j] fmin(fmin(dp[i-1][j],dp[i-1][j-1]),dp[i-1][j1])ma[i][j];//3.初始化 第一行 dp ma[][];//考虑特殊情况int dp[110][110]{{0}};//初始化for(int i 0;in;i){dp[0][i]matrix[0][i];}if(n1){return matrix[0][0];}if(n2){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;in;i){for(int j0;jn;j){if(j1n){//右边界列dp[i][n-1]fmin(dp[i-1][n-1],dp[i-1][n-2])matrix[i][n-1];}else if(j-10){//左边界列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][j1])matrix[i][j];} }}int mm99999;//求最后一行最小值for(int i 1;in;i){mm fmin(fmin(dp[n - 1][i - 1], dp[n - 1][i]),mm);}return mm;
}
