動態(tài)規(guī)劃
- 爬樓梯
回溯法
#include <stdio.h>
class Solution {
public:
int climbStairs(int n) {
if (n == 1 || n == 2){ //遞歸出口，剩下兩節(jié)返回兩種方法
return n;
}
return climbStairs(n-1) + climbStairs(n-2); //遞歸樹分兩枝
}
};
int main(){
Solution solve;
printf("%d\n", solve.climbStairs(3));
return 0;
}
動態(tài)規(guī)劃
第i階的方式數(shù)量 = 第i-1階方式數(shù)量 + 第i-2階方式方式數(shù)量
#include <stdio.h>
#include <vector>
class Solution {
public:
int climbStairs(int n) {
std::vector<int> dp(n + 3, 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];
}
};
int main(){
Solution solve;
printf("%d\n", solve.climbStairs(3));
return 0;
}
盜取財寶搅轿，不能盜相鄰房間
dp[i] = max(dp[i-1],dp[i-2]+nums[i])
#include <stdio.h>
#include <vector>
class Solution {
public:
int rob(std::vector<int>& nums) {
if (nums.size() == 0){ //邊界條件
return 0;
}
if (nums.size() == 1){
return nums[0];
}
std::vector<int> dp(nums.size(), 0); //遞推公式
dp[0] = nums[0];
dp[1] = std::max(nums[0], nums[1]);
for (int i = 2; i < nums.size(); i++){
dp[i] = std::max(dp[i-1], dp[i-2] + nums[i]);
}
return dp[nums.size() - 1];
}
};
int main(){
Solution solve;
std::vector<int> nums;
nums.push_back(5);
nums.push_back(2);
nums.push_back(6);
nums.push_back(3);
nums.push_back(1);
nums.push_back(7);
printf("%d\n", solve.rob(nums));
return 0;
}
最大加和序列
若dp[i-1]>0,dp[i]=dp[i-1]+nums[i]
否則dp[i]=nums[i]
#include <stdio.h>
#include <vector>
class Solution {
public:
int maxSubArray(std::vector<int>& nums) {
std::vector<int> dp(nums.size(), 0);
dp[0] = nums[0]; //邊界條件
int max_res = dp[0];
for (int i = 1; i < nums.size(); i++){
dp[i] = std::max(dp[i-1] + nums[i], nums[i]); //遞推公式
if (max_res < dp[i]){ //找到dp[i]中最大的
max_res = dp[i];
}
}
return max_res;
}
};
int main(){
Solution solve;
std::vector<int> nums;
nums.push_back(-2);
nums.push_back(1);
nums.push_back(-3);
nums.push_back(4);
nums.push_back(-1);
nums.push_back(2);
nums.push_back(1);
nums.push_back(-5);
nums.push_back(4);
printf("%d\n", solve.maxSubArray(nums));
return 0;
}
最小數(shù)值鈔票
當(dāng)i-coins[j] >= 0且dp[i-coins[j]!=-1]時： 表示可以減去相應(yīng)的鈔票值病涨，并且減去后對應(yīng)的數(shù)組元素有值
j = 0,1,2,3,4; coins[j] = 1,2,5,7,10
dp[i] = getmin(dp[i-coins[j]]) + 1 dp[i]就是減去一張鈔票結(jié)果的最小值加一
#include <stdio.h>
#include <vector>
class Solution {
public:
int coinChange(std::vector<int>& coins, int amount) {
std::vector<int> dp;
for (int i = 0; i <= amount; i++){
dp.push_back(-1);
}
dp[0] = 0; //邊界條件
for (int i = 1; i <= amount; i++){
for (int j = 0; j < coins.size(); j++){
if (i - coins[j] >= 0 && dp[i - coins[j]] != -1){ //可以減去相應(yīng)的鈔票值，并且減去后對應(yīng)的數(shù)組元素有值
if (dp[i] == -1 || dp[i] > dp[i - coins[j]] + 1){ //dp[i]為-1或者dp[i]大于當(dāng)前計算的結(jié)果
dp[i] = dp[i - coins[j]] + 1; //更新dp[i]
}
}
}
}
return dp[amount];
}
};
int main(){
Solution solve;
std::vector<int> coins;
coins.push_back(1);
coins.push_back(2);
coins.push_back(5);
coins.push_back(7);
coins.push_back(10);
for (int i = 1; i<= 14; i++){
printf("dp[%d] = %d\n", i, solve.coinChange(coins, i));
}
return 0;
}
三角形璧坟，最小路徑
dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j]
#include <stdio.h>
#include <vector>
class Solution {
public:
int minimumTotal(std::vector<std::vector<int> >& triangle){
if (triangle.size() == 0){
return 0;
}
std::vector<std::vector<int> > dp; //構(gòu)造dp和三角形相同
for (int i = 0; i < triangle.size(); i++){
dp.push_back(std::vector<int>());
for (int j = 0; j < triangle.size(); j++){
dp[i].push_back(0);
}
}
for (int i = 0; i < dp.size(); i++){ //邊界條件既穆，最后一行就是triangle的值
dp[dp.size()-1][i] = triangle[dp.size()-1][i];
}
for (int i = dp.size() - 2; i >= 0; i--){ //遍歷列和行
for (int j = 0; j < dp[i].size(); j++)
dp[i][j] = std::min(dp[i+1][j], dp[i+1][j+1]) //遞推公式
+ triangle[i][j];
}
return dp[0][0];
}
};
int main(){
std::vector<std::vector<int> > triangle;
int test[][10] = {{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
for (int i = 0; i < 4; i++){
triangle.push_back(std::vector<int>());
for (int j = 0; j < i + 1; j++){
triangle[i].push_back(test[i][j]);
}
}
Solution solve;
printf("%d\n", solve.minimumTotal(triangle));
return 0;
}
最長上升子序列
若nums[i]>nums[j]赎懦，說明nums[i]可放置在nums[j]的后面，組成最長上升子序列
若dp[i]<dp[j]+1: dp[i]=dp[j]+1
#include <stdio.h>
#include <vector>
class Solution {
public:
int lengthOfLIS(std::vector<int>& nums) {
if (nums.size() == 0){
return 0;
}
std::vector<int> dp(nums.size(), 0);
dp[0] = 1;
int LIS = 1;
for (int i = 1; i < dp.size(); i++){ //遍歷所有
dp[i] = 1;
for (int j = 0; j < i; j++){ //遍歷之前的
if (nums[i] > nums[j] && dp[i] < dp[j] + 1){ //當(dāng)前數(shù)字能排到某序列后幻工，并且比該序列長度加一小
dp[i] = dp[j] + 1;
}
}
if (LIS < dp[i]){
LIS = dp[i];
}
}
return LIS;
}
};
int main(){
int test[] = {10, 9, 2, 5, 3, 7, 101, 18};
std::vector<int> nums;
for (int i = 0; i < 8; i++){
nums.push_back(test[i]);
}
Solution solve;
printf("%d\n", solve.lengthOfLIS(nums));
return 0;
}
第二種励两，用棧解決
#include <stdio.h>
#include <vector>
class Solution {
public:
int lengthOfLIS(std::vector<int>& nums) {
if (nums.size() == 0){
return 0;
}
std::vector<int> stack;
stack.push_back(nums[0]);
for (int i = 1; i < nums.size(); i++){
if (nums[i] > stack.back()){ //比棧頂大的就入棧
stack.push_back(nums[i]);
}
else{
for (int j = 0; j < stack.size(); j++){ //否則替換棧中第一個比他大的元素
if (stack[j] >= nums[i]){
stack[j] = nums[i];
break;
}
}
}
}
return stack.size();
}
};
int main(){
int test[] = {1, 3, 2, 3, 1, 4};
std::vector<int> nums;
for (int i = 0; i < 6; i++){
nums.push_back(test[i]);
}
Solution solve;
printf("%d\n", solve.lengthOfLIS(nums));
return 0;
}
最小路徑之和
#include <stdio.h>
#include <vector>
class Solution {
public:
int minPathSum(std::vector<std::vector<int> >& grid) {
if (grid.size() == 0){
return 0;
}
int row = grid.size();
int column = grid[0].size();
std::vector<std::vector<int> >
dp(row, std::vector<int>(column, 0));
dp[0][0] = grid[0][0];
for (int i = 1; i < column; i++){ //先初始化第一行
dp[0][i] = dp[0][i-1] + grid[0][i];
}
for (int i = 1; i < row; i++){ //初始化其他
dp[i][0] = dp[i-1][0] + grid[i][0]; //第一列直接加
for (int j = 1; j < column; j++){
dp[i][j] = std::min(dp[i-1][j], dp[i][j-1]) + grid[i][j]; //其他的要對比兩次加的結(jié)果
}
}
return dp[row-1][column-1];
}
};
int main(){
int test[][3] = {{1,3,1}, {1,5,1}, {4,2,1}};
std::vector<std::vector<int> > grid;
for (int i = 0; i < 3; i++){
grid.push_back(std::vector<int>());
for (int j = 0; j < 3; j++){
grid[i].push_back(test[i][j]);
}
}
Solution solve;
printf("%d\n", solve.minPathSum(grid));
return 0;
}
最長公共子序列
dp[i][j] 表示子串A[0...i]（數(shù)組長度為n）和子串B[0...j]（數(shù)組長度為m）的最長公共子序列
當(dāng)A[i] == B[j]時，dp[i][j] = dp[i-1][j-1] + 1;
否則囊颅，dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
最優(yōu)解為dp[n-1][m-1];
https://www.cnblogs.com/fengziwei/p/7827959.html
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextLine()) {
String str1 = scanner.nextLine().toLowerCase();
String str2 = scanner.nextLine().toLowerCase();
System.out.println(findLCS(str1, str1.length(), str2, str2.length()));
}
}
public static int findLCS(String A, int n, String B, int m) {
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
dp[i][j] = 0;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (A.charAt(i - 1) == B.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];
}
}
}
return dp[n][m];
}
}
股票問題
狀態(tài)轉(zhuǎn)移方程:
分為第i天不賣出和賣出
dp[k][i] = max(dp[k][i-1], dp[k-1][j]+price[i] - price[j], j屬于[0,i-1])
