https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html

视频讲解：https://www.bilibili.com/video/BV1ve4y1x7Eu

思路

int **initDP(int m, int n) {int **dp = (int**)malloc(sizeof(int *) * m);int i, j;for(i = 0; i < m; ++i) {dp[i] = (int *)malloc(sizeof(int) * n);}for(i = 0; i < m; ++i)dp[i][0] = 1;for(j = 0; j < n; ++j)dp[0][j] = 1;return dp;
}int uniquePaths(int m, int n){int **dp = initDP(m, n);int i, j;for(i = 1; i < m; ++i) {for(j = 1; j < n; ++j) {dp[i][j] = dp[i-1][j] + dp[i][j-1];}}int result = dp[m-1][n-1];free(dp);return result;
}

学习反思

主要实现了一个计算从起点到终点的唯一路径数的函数uniquePaths。通过动态规划的思想，利用一个二维数组来保存到达每个位置的路径数。函数initDP用于初始化一个大小为m*n的动态规划数组dp，并将起点位置的路径数初始化为1。函数uniquePaths先调用initDP初始化dp数组，然后通过两个for循环遍历dp数组，根据动态规划的递推公式计算每个位置的路径数。最后返回终点位置的路径数，同时释放掉dp数组的内存。时间复杂度为O(mn)，空间复杂度为O(mn)。

思路

int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){int m = obstacleGridSize;int n = obstacleGridColSize[0];int *dp = (int*)malloc(sizeof(int) * n);int i, j;for (j = 0; j < n; ++j) {if (obstacleGrid[0][j] == 1)dp[j] = 0;else if (j == 0)dp[j] = 1;elsedp[j] = dp[j - 1];}for (i = 1; i < m; ++i) {for (j = 0; j < n; ++j) {if (obstacleGrid[i][j] == 1)dp[j] = 0;else if (j != 0)dp[j] += dp[j - 1];}}return dp[n - 1];
}

学习反思

在原有的uniquePaths基础上，添加了一个障碍物的判断条件。obstacleGrid是一个二维数组，表示地图，其中1表示障碍物，0表示可通行的路径。函数uniquePathsWithObstacles通过动态规划的思想，利用一个一维数组dp来保存到达每个位置的路径数。首先，根据障碍物的情况初始化第一行的路径数，如果遇到障碍物，则该位置的路径数为0，否则，第一行的路径数与前一个位置的路径数相同。然后，从第二行开始遍历，对于每个位置，如果遇到障碍物，则将该位置的路径数设为0；否则，将该位置的路径数更新为前一个位置的路径数与当前位置的路径数之和。最后，返回dp数组的最后一个元素，即终点位置的路径数。时间复杂度为O(m*n)，空间复杂度为O(n)。

343.整数拆分

思路

int *initDP(int num) {int* dp = (int*)malloc(sizeof(int) * (num + 1));int i;for(i = 0; i < num + 1; ++i) {dp[i] = 0;}return dp;
}
int max(int num1, int num2, int num3) {int tempMax = num1 > num2 ? num1 : num2;return tempMax > num3 ? tempMax : num3;
}
int integerBreak(int n){int *dp = initDP(n);dp[2] = 1;int i;for(i = 3; i <= n; ++i) {int j;for(j = 1; j < i - 1; ++j) {      dp[i] = max(dp[i], j * (i - j), j * dp[i - j]);}}return dp[n];
}

学习反思

动态规划的例子，用于解决整数拆分问题。给定一个正整数n，拆分成至少两个正整数的和，并使得拆分后的正整数的乘积最大。函数integerBreak返回拆分后的正整数的乘积的最大值。函数initDP用于初始化一个大小为num + 1的数组dp，并将所有元素初始化为0。函数max用于返回三个数中的最大值。函数integerBreak通过动态规划的思想，遍历从3到n的所有整数，对于每个整数i，遍历从1到i - 1的所有整数j，并更新dp[i]的值。dp[i]的值表示将整数i拆分后的最大乘积。对于每个整数i，计算j * (i - j)以及j * dp[i - j]的最大值，并将其与dp[i]的值比较，更新dp[i]的值。最后，返回dp[n]的值，即拆分后的正整数的乘积的最大值。该代码的时间复杂度为O(n^2)，空间复杂度为O(n)。

总结

动态规划，加油！！！