一维动态规划
一维动态规划
509. 斐波那契数
int *dp;
// 自顶向下记忆化搜索，时间复杂度O（n）
int recursive(int n) {
if (n == 0)return 0;
if (n == 1) return 1;
// 若之前计算过就直接返回
if (dp[n] != -1) return dp[n];
dp[n] = recursive(n - 2) + recursive(n - 1);
return dp[n];
}
int fib(int n) {
dp = (int *) malloc(sizeof(int) * (n + 1));
memset(dp, -1, sizeof(int) * (n + 1));
return recursive(n);
}
// 自下而上，时间复杂度O（n）
int fib(int n) {
int dp[31];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; ++i)
// 状态转移方程
dp[i] = dp[i - 2] + dp[i - 1];
return dp[n];
}
// 状态压缩，时间复杂度O（n）
int fib(int n) {
if (n < 2) return n;
int left = 0;
int mid = 1;
int right;
for (int i = 2; i <= n; ++i) {
right = left + mid;
left = mid;
mid = right;
}
return right;
}
// todo 矩阵快速幂，时间复杂度O（logn）
// 代入通项公式
int fib(int n) {
double sqrt5 = sqrt(5);
double fibN = pow((1 + sqrt5) / 2, n) - pow((1 - sqrt5) / 2, n);
// 四舍五入成正数
return round(fibN / sqrt5);
}
// 打表
983. 最低票价
// 每种方案对应的通行天数
int durations[3] = {1, 7, 30};
int min(int a, int b) {
return a > b ? b : a;
}
// 返回从第day[i]天开始往后的行程全部完成所需的最小花费
int recursive(int *days, int daysSize, int *costs, int curIndex) {
if (curIndex == daysSize) return 0;
int res = 0x7fffffff;
// 一共三种方案
for (int i = 0; i < 3; ++i) {
// day[index]为下一个需要买票的日子
int index = curIndex;
// 可以连续通行的最后一天的后一天
int nextDay = days[index] + durations[i];
while (index < daysSize && days[index] < nextDay)
index++;
// 记录最小值
res = min(res, costs[i] + recursive(days, daysSize, costs, index));
}
return res;
}
// 暴力法超时，时间复杂度O（3^n）
int mincostTickets(int *days, int daysSize, int *costs, int costsSize) {
return recursive(days, daysSize, costs, 0);
}
// 每种方案对应的通行天数
int durations[3] = {1, 7, 30};
int *dp;
int min(int a, int b) {
return a > b ? b : a;
}
// 返回从第day[i]天开始往后的行程全部完成所需的最小花费
int recursive(int *days, int daysSize, int *costs, int curIndex) {
if (curIndex == daysSize) return 0;
if (dp[curIndex] != 0x7fffffff) return dp[curIndex];
int res = 0x7fffffff;
// 一共三种方案
for (int i = 0; i < 3; ++i) {
// day[index]为下一个需要买票的日子
int index = curIndex;
// 可以连续通行的最后一天的后一天
int nextDay = days[index] + durations[i];
while (index < daysSize && days[index] < nextDay)
index++;
// 记录最小值
res = min(res, costs[i] + recursive(days, daysSize, costs, index));
}
dp[curIndex] = res;
return res;
}
// 记忆化搜索，时间复杂度O（3n）=O（n）
int mincostTickets(int *days, int daysSize, int *costs, int costsSize) {
dp = (int *) malloc(sizeof(int) * daysSize);
for (int i = 0; i < daysSize; ++i) dp[i] = 0x7fffffff;
return recursive(days, daysSize, costs, 0);
}
int min(int a, int b) {
return a > b ? b : a;
}
// 自下而上
int mincostTickets(int *days, int daysSize, int *costs, int costsSize) {
// 每种方案对应的通行天数
int durations[3] = {1, 7, 30};
int dp[daysSize + 1];
for (int i = 0; i < daysSize; ++i) dp[i] = 0x7fffffff;
dp[daysSize] = 0;
for (int curIndex = daysSize - 1; curIndex >= 0; curIndex--) {
// 一共三种方案
for (int i = 0; i < 3; ++i) {
// day[index]为下一个需要买票的日子
int index = curIndex;
// 可以连续通行的最后一天的后一天
int nextDay = days[index] + durations[i];
while (index < daysSize && days[index] < nextDay)
index++;
// 记录最小值
dp[curIndex] = min(dp[curIndex], dp[index] + costs[i]);
}
}
return dp[0];
}
91. 解码方法
int len;
// 返回从curIndex位置往后的字符串有多少种解码方式
int recursive(char *s, int curIndex) {
// 返回1表示到末尾结束了，之前的解码算是一种方案
if (curIndex == len) return 1;
int res;
// 当前位置是0，无法解码
if (s[curIndex] == '0') {
res = 0;
} else {
// i位置可以对应一个字符
res = recursive(s, curIndex + 1);
int val = (s[curIndex] - '0') * 10 + (s[curIndex + 1] - '0');
if (curIndex + 1 < len && val <= 26)
// i和i+1位置合在一起也能构成一个字母
res += recursive(s, curIndex + 2);
}
return res;
}
// 暴力法超时，O（2^n）
int numDecodings(char *s) {
len = strlen(s);
return recursive(s, 0);
}
int len;
int *dp;
// 返回从curIndex位置往后的字符串有多少种解码方式
int recursive(char *s, int curIndex) {
// 返回1表示到末尾结束了，之前的解码算是一种方案
if (curIndex == len) return 1;
if (dp[curIndex] != -1) return dp[curIndex];
int res;
// 当前位置是0，无法解码
if (s[curIndex] == '0') {
res = 0;
} else {
// curIndex位置可以对应一个字符
res = recursive(s, curIndex + 1);
if (curIndex + 1 < len && (s[curIndex] - '0') * 10 + (s[curIndex + 1] - '0') <= 26)
// curIndex和curIndex+1位置合在一起也能构成一个字母
res += recursive(s, curIndex + 2);
}
dp[curIndex] = res;
return res;
}
// 记忆化搜索，O（n）
int numDecodings(char *s) {
len = strlen(s);
dp = (int *) malloc(sizeof(int) * len);
memset(dp, -1, sizeof(int) * len);
return recursive(s, 0);
}
int numDecodings(char *s) {
int len = strlen(s);;
int *dp = (int *) malloc(sizeof(int) * (len + 1));
dp[len] = 1;
for (int curIndex = len - 1; curIndex >= 0; curIndex--) {
if (s[curIndex] == '0') {
// 当前位置是0，无法解码
dp[curIndex] = 0;
} else {
// curIndex位置可以对应一个字符
dp[curIndex] = dp[curIndex + 1];
if (curIndex + 1 < len && (s[curIndex] - '0') * 10 + (s[curIndex + 1] - '0') <= 26)
// curIndex和curIndex+1位置合在一起也能构成一个字母
dp[curIndex] += dp[curIndex + 2];
}
}
return dp[0];
}
// 状态压缩
// 类似有条件的斐波那契数列
int numDecodings(char *s) {
int len = strlen(s);;
int left, mid = 1, right;
for (int curIndex = len - 1; curIndex >= 0; curIndex--) {
if (s[curIndex] == '0') {
// 当前位置是0，无法解码
left = 0;
} else {
// curIndex位置可以对应一个字符
left = mid;
if (curIndex + 1 < len && (s[curIndex] - '0') * 10 + (s[curIndex + 1] - '0') <= 26)
// curIndex和curIndex+1位置合在一起也能构成一个字母
left += right;
}
right = mid;
mid = left;
}
return left;
}
639. 解码方法 II
待归类
70. 爬楼梯
int climbStairs(int n) {
int dp[46];
// 一次爬一层，只有一种方法
dp[1] = 1;
// 两次爬一层或者一次爬两层，一共两种方法
dp[2] = 2;
int i = 3;
while (i <= n) {
// i层可由i-2层爬两个台阶到达，或者由i-1层爬一个台阶到达
// 爬到i层的方法总数为这两种爬法的方法总数和
dp[i] = dp[i - 2] + dp[i - 1];
i++;
}
return dp[n];
}
// 空间复杂度O（1）
int climbStairs(int n) {
if (n < 3) return n;
int left = 1;
int mid = 2;
int right;
int count = n - 2;
while (count-- > 0) {
right = left + mid;
left = mid;
mid = right;
}
return right;
}
62. 不同路径
int uniquePaths(int m, int n) {
// 记录到格子（i，j）的路径总数
int dp[m][n];
// 初始条件
// 从（0，0）到第一列的任何一个格子的路径只有一条，就是从上往下
for (int i = 0; i < m; ++i) dp[i][0] = 1;
// 从（0，0）到第一行的任何一个格子的路径只有一条，就是从左往右
for (int i = 0; i < n; ++i) dp[0][i] = 1;
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
// 状态转移方程
// （i，j）只能由左边的格子或者上面的格子走过来，dp[i][j]就是这两种途径的路径和
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
// todo 空间优化
// 排列组合
第 N 个泰波那契数
int tribonacci(int n){
if (n < 2) return n;
if (n == 2) return 1;
// 初始条件
int left = 0;
int midLeft = 1;
int midRight = 1;
int right;
int count = n - 2;
while (count-- > 0) {
right = left + midLeft + midRight;
left = midLeft;
midLeft = midRight;
midRight = right;
}
return right;
}
// todo 矩阵快速幂
目标和
int res;
// 暴力递归
void dfs(int *nums, int numsSize, int target, int index, int tempSum) {
if (index == numsSize - 1) {
if (tempSum + nums[index] == target) res++;
if (tempSum - nums[index] == target) res++;
return;
}
dfs(nums, numsSize, target, index + 1, tempSum + nums[index]);
dfs(nums, numsSize, target, index + 1, tempSum - nums[index]);
}
int findTargetSumWays(int *nums, int numsSize, int target) {
res = 0;
dfs(nums, numsSize, target, 0, 0);
return res;
}
// todo
热门相关：霸宠天下：腹黑帝君妖娆后 锦衣当国 暖君 暖君 史上第一宠婚：慕少的娇妻