动态规划c++

动态规划

爬楼梯

int climbStairs(int n) { int dp[n+2]; int i; if(0 == n) { return 0; } if(1 == n) { return 1; } if(2 == n) { return 2; } dp[0] = 0; dp[1] = 1; dp[2] = 2; for(i=3;i <=n; i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n];}

杨辉三角

/*把杨辉三角的每一排左对齐：​ [1][1,1][1,2,1][1,3,3,1][1,4,6,4,1]​ 设要计算的二维数组是 c，计算方法如下：每一排的第一个数和最后一个数都是 1，即 c[i][0]=c[i][i]=1。其余数字，等于左上方的数，加上正上方的数，即 c[i][j]=c[i−1][j−1]+c[i−1][j]。例如 4=1+3, 6=3+3 等。*/class Solution {public: vector<vector> generate(int numRows) { vector<vector> c(numRows); for(int i = 0; i < numRows; i++) { c[i].resize(i+1,1); for(int j = 1; j < i; j++) { c[i][j] = c[i-1][j-1] + c[i-1][j]; } } return c; }};

小偷问题

/*k 个房子中最后一个房子是 H k−1​ 。如果不偷这个房子，那么问题就变成在前 k−1 个房子中偷到最大的金额，也就是子问题 f(k−1)。如果偷这个房子，那么前一个房子 H k−2​ 显然不能偷，其他房子不受影响。那么问题就变成在前 k−2 个房子中偷到的最大的金额。两种情况中，选择金额较大的一种结果。f(k)=max{f(k−1),Hk−1+f(k−2)}在写递推关系的时候，要注意写上 k=0 和 k=1 的基本情况：当 k=0 时，没有房子，所以 f(0)=0。当 k=1 时，只有一个房子，偷这个房子即可，所以 f(1)=H 0​*/class Solution {public: int rob(vector& nums) { int size = nums.size(); if(0 == size) { return 0; } vector c(size+2,0); c[0] = 0; c[1] = nums[0]; for(int i = 2; i  (c[i-2] + nums[i-1])) { c[i] = c[i-1]; } else { c[i] = c[i-2] + nums[i-1]; } } return c[size]; }};

完全平方数之和

// 动态规划 // 类似1、4、9、16 这种就是完全平方数，本题就是以尽可能少的完全平方数累加出 n// 写出状态表达式 f(i) 表示最少需要多少个完全平方数来表示整数i，其中构成i的所有数 j 一定在区间 [1, i^0.5] 内// 状态转移方程：f(i) = 1 + min f(i - j^2) (j属于1~i^0.5) // f(i) = min{f(i-1²), f(i-2²), ..., f(i-j²)} + 1class Solution {public: int numSquares(int n) { vector c(n+1); int minNUM = 0; for(int i = 1; i <=n; i++) { minNUM = INT_MAX; for(int j = 1; j*j <= i; ++j) { minNUM = min(minNUM,c[i-j*j]); } c[i] = minNUM + 1; } return c[n]; }};

完全背包（零钱兑换）

/*第一步确定好状态：dp[i]表示组成金额i所需的最少硬币数第二步确定好初始状态: dp[0]=0遍历硬币，数额小于i,value[i] = min(value[i],value[i-coin]+1);*/class Solution {public: int coinChange(vector& coins, int amount) { vector value(amount+1,amount+1); value[0] = 0; for(int i = 1; i <=amount; i++) { for(int coin:coins) { if(coin  amount ? -1 : value[amount]; }};

单词拆分

/*哈希集合的创建C++unordered_set word_dict(wordDict.begin(), wordDict.end());子串s.substr(j,i-j)表示从字符串s的索引j开始，截取长度为i-j的子字符串。例如，如果s=\"applepenapple\"，j=5，i=8，那么s.substr(5, 3)的结果是\"pen\"。查找word_dict.find(s.substr(j,i-j)) 是一个查找操作：如果word_dict是unordered_set，find会返回一个迭代器，指向找到的元素；如果未找到，则返回word_dict.end()。*/class Solution {public: bool wordBreak(string s, vector& wordDict) { unordered_set word_dict(wordDict.begin(),wordDict.end()); int n = s.size(); vector f(n+1); f[0] = true; for(int i = 1; i <=n; i++) { for(int j = 0; j < i;j++) { if(f[j] && word_dict.find(s.substr(j,i-j))!=word_dict.end()) {  f[i] = true;  break; } } } return f[n]; }};

最大子数组和

class Solution {public: int maxSubArray(vector& nums) { vector value(nums.size() + 1,0); if(0 == nums.size()) { return 0; } value[0] = nums[0]; int maxvalue = nums[0]; // cout <<\"初始值maxvalue = \" << maxvalue <<endl; for(int i = 1; i < nums.size();i++) { value[i] = max(value[i-1],0) + nums[i]; maxvalue = max(maxvalue,value[i]); // cout << \"i = \" << i << \" value = \" << value[i] << \" maxvalue = \" << maxvalue <<endl; } return maxvalue; }};

乘积最大子数组

class Solution {public: int maxProduct(vector& nums) { int n = nums.size(); vector f_max(n); vector f_min(n); f_max[0] = f_min[0] = nums[0]; // int maxvalue = 0; for(int i = 1; i < n; i++) { int x = nums[i]; f_max[i] = max({f_max[i-1]*x, f_min[i-1]*x, x}); f_min[i] = min({f_max[i-1]*x, f_min[i-1]*x, x}); // maxvalue = max(maxvalue,f_max[i]); } sort(f_max.begin(),f_max.end()); return f_max[n-1]; }};

买卖股票最佳时机

int maxProfit(int* prices, int pricesSize) { if (pricesSize < 2) return 0; int i = 0, max = 0, dp[pricesSize]; dp[i] = 0; for (i = 1; i  max ? dp[i] : max; //记录dp数组中出现的最大数 } return max;}作者：pavedplaza链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/solutions/2926151/dai-ma-jian-duan-zhuang-tai-zhuan-yi-fan-a93a/来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

最长递增子序列

确定dp数组以及下标含义：
dp[i] 为考虑前 i 个元素，以第 i 个数字结尾的最长上升子序列的长度，注意 nums[i] 必须被选取。
状态转移方程： 设 j∈[0,i)，考虑每轮计算新 dp[i] 时，遍历 [0,i) 列表区间，做以下判断：
当 nums[i]>nums[j] 时： nums[i] 可以接在 nums[j] 之后（此题要求严格递增），此情况下最长上升子序列长度为 dp[j]+1 ；
当 nums[i]<=nums[j] 时： nums[i] 无法接在 nums[j] 之后，此情况上升子序列不成立，跳过。
上述所有 1. 情况 下计算出的 dp[j]+1 的最大值，为直到 i 的最长上升子序列长度（即 dp[i] ）。实现方式为遍历 j 时，每轮执行 dp[i]=max(dp[i],dp[j]+1)。
转移方程： dp[i]=max(dp[i],dp[j]+1) for j in [0,i)。

int lengthOfLIS(int* nums, int numsSize) { int length = 1; int *dp = (int *)malloc(sizeof(int) * numsSize); for(int i = 0; i < numsSize;i++) { dp[i] = 1; } for(int i = 1; i < numsSize;i++) { for(int j = 0; j nums[j]) { dp[i] = fmax(dp[i],dp[j]+1); } } length = fmax(length,dp[i]); } return length;}

int minPathSum(int** grid, int gridSize, int* gridColSize) { if(0 == gridSize || 0 == *gridColSize) { return 0; } int dp[gridSize][*gridColSize]; int i; int j; dp[0][0] = grid[0][0]; for(i = 1; i < *gridColSize; i++) { dp[0][i] = dp[0][i-1] + grid[0][i]; } for(i = 1; i <gridSize; i++) { dp[i][0] = dp[i-1][0] + grid[i][0]; } for(i = 1; i < gridSize;i++) { for(j = 1; j < *gridColSize; j++) { dp[i][j] = (dp[i-1][j] < dp[i][j-1] ? dp[i-1][j] : dp[i][j-1]) + grid[i][j]; } } return dp[i-1][j-1];}

int minPathSum(int** grid, int gridSize, int* gridColSize) { if(0 == gridSize || 0 == *gridColSize) { return 0; } int dp[gridSize][*gridColSize]; int i; int j; dp[0][0] = grid[0][0]; for(i = 1; i < *gridColSize; i++) { dp[0][i] = dp[0][i-1] + grid[0][i]; } for(i = 1; i <gridSize; i++) { dp[i][0] = dp[i-1][0] + grid[i][0]; } for(i = 1; i < gridSize;i++) { for(j = 1; j < *gridColSize; j++) { dp[i][j] = (dp[i-1][j] < dp[i][j-1] ? dp[i-1][j] : dp[i][j-1]) + grid[i][j]; } } return dp[i-1][j-1];}

int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize) { // int minPathSum(int** grid, int gridSize, int* gridColSize) { if(0 == obstacleGridSize || 0 == *obstacleGridColSize) { return 0; } int dp[obstacleGridSize][*obstacleGridColSize]; int i; int j;// dp[0][0] = obstacleGrid[0][0]; bool flag = true; for(i = 0; i < *obstacleGridColSize; i++) { if(true == flag && 1 != obstacleGrid[0][i]) { dp[0][i] = 1; } else if (obstacleGrid[0][i] == 1) { dp[0][i] = 0; flag = false; } else { dp[0][i] = 0; } } flag = true; for(i = 0; i <obstacleGridSize; i++) { if(true == flag && 1 != obstacleGrid[i][0]) { dp[i][0] = 1; } else if(1 == obstacleGrid[i][0]) { dp[i][0] = 0; flag = false; } else { dp[i][0] = 0; } } for(i = 1; i < obstacleGridSize;i++) { for(j = 1; j < *obstacleGridColSize; j++) { if(1 == obstacleGrid[i][j]) { dp[i][j] = 0; } else { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; }  } } return dp[i-1][j-1];}// }

int min(int a, int b) { return (a  b) ? a : b;}int calculateMinimumHP(int** dungeon, int dungeonSize, int* dungeonColSize){ int R = dungeonSize, C = *dungeonColSize; int dp[R][C]; /* dp[i][j]:到达第i行第j个格子前需要的最低hp */ /* dp[i][j] + dungeon[i][j] >= dp[i + 1][j] */ /* dp[i][j] + dungeon[i][j] >= dp[i][j + 1] */ /* 上述两个式子满足其一即可，以及要保证任何时候的dp都是大于0的 */ dp[R - 1][C - 1] = 1 - min(dungeon[R - 1][C - 1], 0); for (int i = R - 2; i >= 0; i--)  /* 初始化最后一列 */ dp[i][C - 1] = max(dp[i + 1][C - 1] - dungeon[i][C - 1], 1); for (int i = C - 2; i >= 0; i--)  /* 初始化最后一行 */ dp[R - 1][i] = max(dp[R - 1][i + 1] - dungeon[R - 1][i], 1); for (int i = R - 2; i >= 0; i--) for (int j = C - 2; j >= 0; j--) dp[i][j] = max(min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j], 1); return dp[0][0];}作者：HUST_V链接：https://leetcode.cn/problems/dungeon-game/solutions/104597/dong-tai-gui-hua-cyu-yan-by-npu_v/来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

char * longestPalindrome(char * s){ //回文串结束下标 int j; //最长回文串长度 int maxLength = 1; //回文串起始位置 int begin = 0; int len = strlen(s); // dp[i][j] 表示 s[i..j] 是否是回文串 bool dp[len][len]; //0.初始化：所有长度为 1 的子串都是回文串 for (int i = 0; i < len; i++) { dp[i][i] = true; } //1.长度为 1 的一定是回文串，故长度从 2 开始 for(int l = 2; l <= len; l++){ //2.起始位置从 0 开始 for(int i = 0; i = len) { break; } //回文串首尾字母不相同 if (s[i] != s[j]) { dp[i][j] = false; } else { //回文串小于 3 个字符（ 3 个字符内首尾相等即为回文串） if (j - i  maxLength) { maxLength = l; begin = i; } } } //设置结束位置 s[begin + maxLength] = \'\\0\'; return s + begin;}作者：lotushint链接：https://leetcode.cn/problems/longest-palindromic-substring/solutions/1754391/by-sleepy-i3abbagesrd-o3fi/来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {public: bool canPartition(vector& nums) { /* nums大小判断 */ if(nums.size() < 2) return false; /* 计算目标值即背包容量 */ int sum = 0; int bagWight = 0; for(int i = 0; i < nums.size(); i++){ sum += nums[i]; } /* 和不能为奇数 */ if(sum%2 == 1) return false; /* 计算背包容量 */ bagWight = sum/2; /* 定义dp数组 并初始化数组全部为0 */ vector<vector> dp(nums.size(),vector(bagWight + 1,0)); for(int i = 1; i < nums.size(); i++) { for(int j = 0; j <= bagWight; j++) { if(j < nums[i-1]) dp[i][j] = dp[i-1][j]; else dp[i][j] = max(dp[i-1][j], dp[i-1][j - nums[i-1]] + nums[i-1]); } } if(dp[nums.size()-1][bagWight] == bagWight) return true; return false; }};

class Solution {public: int longestValidParentheses(string s) { int size = s.length(); vector dp(size, 0); int maxVal = 0; for(int i = 1; i = 0) { dp[i] = dp[i] + dp[i - 2];  } } else if (dp[i - 1] > 0) {  if ((i - dp[i - 1] - 1) >= 0 && s[i - dp[i - 1] - 1] == \'(\') { dp[i] = dp[i - 1] + 2; if ((i - dp[i - 1] - 2) >= 0) { dp[i] = dp[i] + dp[i - dp[i - 1] - 2]; }  } } } maxVal = max(maxVal, dp[i]); } return maxVal; }};

class Solution {public: int uniquePaths(int m, int n) { // 动态规划 // 本题要从（0，0）走到（i，j），i的范围是[0, m) ，j的范围是[0, n) // 状态转移变量：f(i, j)表示从左上角走到（i，j）的不同路径数量 // 状态转移方程：f(i, j) = f(i-1, j) + f(i, j-1); // 优化：由于 f(i,j) 仅与第 i 行和第 i−1 行的状态有关，因此可以使用滚动数组代替二维数组，使空间复杂度降低为 O(n) vector f(n, 1); // 循环从1开始，因为不管是 第0行 还是 第0列 ，走到这一格的路径数一定是1，因为题目说了只能往右和往下走 for(int i = 1; i < m; ++i) { for(int j = 1; j < n; ++j) { f[j] += f[j-1]; } } return f[n-1]; }};

class Solution {public: int longestCommonSubsequence(string text1, string text2) { int n = text1.size(), m = text2.size(); vector<vector> f(n + 1, vector(m + 1, 0)); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (text1[i - 1] == text2[j - 1]) {  f[i][j] = f[i - 1][j - 1] + 1; } else {  f[i][j] = max(f[i - 1][j], f[i][j - 1]); } } } return f[n][m]; }};

class Solution {public: int minDistance(string word1, string word2) { vector<vector> dp(word1.size() + 1, vector(word2.size() + 1, 0)); for (int i = 0; i < dp.size(); i++) { dp[i][0] = i; } for (int j = 0; j < dp[0].size(); j++) { dp[0][j] = j; } for (int i = 1; i < dp.size(); i++) { for (int j = 1; j < dp[i].size(); j++) { dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1; if (word1[i - 1] == word2[j - 1]) {  dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]); } } } return dp.back().back(); }};