Skip to content

Commit 25c40c3

Browse files
coderonioncoderonion
committed
update
1 parent 6b012bf commit 25c40c3

12 files changed

+70
-70
lines changed

‎chapter_dynamic_programming/climbing_stairs_backtrack.zig

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,7 +23,7 @@ fn backtrack(choices: []i32, state: i32, n: i32, res: std.ArrayList(i32)) void {
2323
}
2424

2525
// 爬楼梯：回溯
26-
fn climbing_stairs_backtrack(n: usize) !i32 {
26+
fn climbingStairsBacktrack(n: usize) !i32 {
2727
var choices = [_]i32{ 1, 2 }; // 可选择向上爬 1 或 2 阶
2828
var state: i32 = 0; // 从第 0 阶开始爬
2929
var res = std.ArrayList(i32).init(std.heap.page_allocator);
@@ -37,7 +37,7 @@ fn climbing_stairs_backtrack(n: usize) !i32 {
3737
pub fn main() !void {
3838
var n: usize = 9;
3939

40-
var res = try climbing_stairs_backtrack(n);
40+
var res = try climbingStairsBacktrack(n);
4141
std.debug.print("爬 {} 阶楼梯共有 {} 种方案\n", .{ n, res });
4242

4343
_ = try std.io.getStdIn().reader().readByte();

‎chapter_dynamic_programming/climbing_stairs_constraint_dp.zig

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@
55
const std = @import("std");
66

77
// 带约束爬楼梯：动态规划
8-
fn climbing_stairs_constraint_dp(comptime n: usize) i32 {
8+
fn climbingStairsConstraintDp(comptime n: usize) i32 {
99
if (n == 1 or n == 2) {
1010
return @intCast(n);
1111
}
@@ -28,7 +28,7 @@ fn climbing_stairs_constraint_dp(comptime n: usize) i32 {
2828
pub fn main() !void {
2929
comptime var n: usize = 9;
3030

31-
var res = climbing_stairs_constraint_dp(n);
31+
var res = climbingStairsConstraintDp(n);
3232
std.debug.print("爬 {} 阶楼梯共有 {} 种方案\n", .{ n, res });
3333

3434
_ = try std.io.getStdIn().reader().readByte();

‎chapter_dynamic_programming/climbing_stairs_dfs.zig

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -16,15 +16,15 @@ fn dfs(i: usize) i32 {
1616
}
1717

1818
// 爬楼梯：搜索
19-
fn climbing_stairs_dfs(comptime n: usize) i32 {
19+
fn climbingStairsDfs(comptime n: usize) i32 {
2020
return dfs(n);
2121
}
2222

2323
// Driver Code
2424
pub fn main() !void {
2525
comptime var n: usize = 9;
2626

27-
var res = climbing_stairs_dfs(n);
27+
var res = climbingStairsDfs(n);
2828
std.debug.print("爬 {} 阶楼梯共有 {} 种方案\n", .{ n, res });
2929

3030
_ = try std.io.getStdIn().reader().readByte();

‎chapter_dynamic_programming/climbing_stairs_dfs_mem.zig

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -22,7 +22,7 @@ fn dfs(i: usize, mem: []i32) i32 {
2222
}
2323

2424
// 爬楼梯：记忆化搜索
25-
fn climbing_stairs_dfs_mem(comptime n: usize) i32 {
25+
fn climbingStairsDfsMem(comptime n: usize) i32 {
2626
// mem[i] 记录爬到第 i 阶的方案总数，-1 代表无记录
2727
var mem = [_]i32{ -1 } ** (n + 1);
2828
return dfs(n, &mem);
@@ -32,7 +32,7 @@ fn climbing_stairs_dfs_mem(comptime n: usize) i32 {
3232
pub fn main() !void {
3333
comptime var n: usize = 9;
3434

35-
var res = climbing_stairs_dfs_mem(n);
35+
var res = climbingStairsDfsMem(n);
3636
std.debug.print("爬 {} 阶楼梯共有 {} 种方案\n", .{ n, res });
3737

3838
_ = try std.io.getStdIn().reader().readByte();

‎chapter_dynamic_programming/climbing_stairs_dp.zig

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@
55
const std = @import("std");
66

77
// 爬楼梯：动态规划
8-
fn climbing_stairs_dp(comptime n: usize) i32 {
8+
fn climbingStairsDp(comptime n: usize) i32 {
99
// 已知 dp[1] 和 dp[2] ，返回之
1010
if (n == 1 or n == 2) {
1111
return @intCast(n);
@@ -23,7 +23,7 @@ fn climbing_stairs_dp(comptime n: usize) i32 {
2323
}
2424

2525
// 爬楼梯：状态压缩后的动态规划
26-
fn climbing_stairs_dp_comp(comptime n: usize) i32 {
26+
fn climbingStairsDpComp(comptime n: usize) i32 {
2727
if (n == 1 or n == 2) {
2828
return @intCast(n);
2929
}
@@ -41,10 +41,10 @@ fn climbing_stairs_dp_comp(comptime n: usize) i32 {
4141
pub fn main() !void {
4242
comptime var n: usize = 9;
4343

44-
var res = climbing_stairs_dp(n);
44+
var res = climbingStairsDp(n);
4545
std.debug.print("爬 {} 阶楼梯共有 {} 种方案\n", .{ n, res });
4646

47-
res = climbing_stairs_dp_comp(n);
47+
res = climbingStairsDpComp(n);
4848
std.debug.print("爬 {} 阶楼梯共有 {} 种方案\n", .{ n, res });
4949

5050
_ = try std.io.getStdIn().reader().readByte();

‎chapter_dynamic_programming/coin_change.zig

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@
55
const std = @import("std");
66

77
// 零钱兑换：动态规划
8-
fn coin_change_dp(comptime coins: []i32, comptime amt: usize) i32 {
8+
fn coinChangeDp(comptime coins: []i32, comptime amt: usize) i32 {
99
comptime var n = coins.len;
1010
comptime var max = amt + 1;
1111
// 初始化 dp 表
@@ -34,7 +34,7 @@ fn coin_change_dp(comptime coins: []i32, comptime amt: usize) i32 {
3434
}
3535

3636
// 零钱兑换：状态压缩后的动态规划
37-
fn coin_change_dp_comp(comptime coins: []i32, comptime amt: usize) i32 {
37+
fn coinChangeDpComp(comptime coins: []i32, comptime amt: usize) i32 {
3838
comptime var n = coins.len;
3939
comptime var max = amt + 1;
4040
// 初始化 dp 表
@@ -66,11 +66,11 @@ pub fn main() !void {
6666
comptime var amt: usize = 4;
6767

6868
// 动态规划
69-
var res = coin_change_dp(&coins, amt);
69+
var res = coinChangeDp(&coins, amt);
7070
std.debug.print("凑到目标金额所需的最少硬币数量为 {}\n", .{res});
7171

7272
// 状态压缩后的动态规划
73-
res = coin_change_dp_comp(&coins, amt);
73+
res = coinChangeDpComp(&coins, amt);
7474
std.debug.print("凑到目标金额所需的最少硬币数量为 {}\n", .{res});
7575

7676
_ = try std.io.getStdIn().reader().readByte();

‎chapter_dynamic_programming/coin_change_ii.zig

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@
55
const std = @import("std");
66

77
// 零钱兑换 II：动态规划
8-
fn coin_change_ii_dp(comptime coins: []i32, comptime amt: usize) i32 {
8+
fn coinChangeIIDp(comptime coins: []i32, comptime amt: usize) i32 {
99
comptime var n = coins.len;
1010
// 初始化 dp 表
1111
var dp = [_][amt + 1]i32{[_]i32{0} ** (amt + 1)} ** (n + 1);
@@ -29,7 +29,7 @@ fn coin_change_ii_dp(comptime coins: []i32, comptime amt: usize) i32 {
2929
}
3030

3131
// 零钱兑换 II：状态压缩后的动态规划
32-
fn coin_change_dp_ii_comp(comptime coins: []i32, comptime amt: usize) i32 {
32+
fn coinChangeIIDpComp(comptime coins: []i32, comptime amt: usize) i32 {
3333
comptime var n = coins.len;
3434
// 初始化 dp 表
3535
var dp = [_]i32{0} ** (amt + 1);
@@ -55,11 +55,11 @@ pub fn main() !void {
5555
comptime var amt: usize = 5;
5656

5757
// 动态规划
58-
var res = coin_change_ii_dp(&coins, amt);
58+
var res = coinChangeIIDp(&coins, amt);
5959
std.debug.print("凑出目标金额的硬币组合数量为 {}\n", .{res});
6060

6161
// 状态压缩后的动态规划
62-
res = coin_change_dp_ii_comp(&coins, amt);
62+
res = coinChangeIIDpComp(&coins, amt);
6363
std.debug.print("凑出目标金额的硬币组合数量为 {}\n", .{res});
6464

6565
_ = try std.io.getStdIn().reader().readByte();

‎chapter_dynamic_programming/edit_distance.zig

Lines changed: 16 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@
55
const std = @import("std");
66

77
// 编辑距离：暴力搜索
8-
fn edit_distance_dfs(comptime s: []const u8, comptime t: []const u8, i: usize, j: usize) i32 {
8+
fn editDistanceDfs(comptime s: []const u8, comptime t: []const u8, i: usize, j: usize) i32 {
99
// 若 s 和 t 都为空，则返回 0
1010
if (i == 0 and j == 0) {
1111
return 0;
@@ -20,18 +20,18 @@ fn edit_distance_dfs(comptime s: []const u8, comptime t: []const u8, i: usize, j
2020
}
2121
// 若两字符相等，则直接跳过此两字符
2222
if (s[i - 1] == t[j - 1]) {
23-
return edit_distance_dfs(s, t, i - 1, j - 1);
23+
return editDistanceDfs(s, t, i - 1, j - 1);
2424
}
2525
// 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
26-
var insert = edit_distance_dfs(s, t, i, j - 1);
27-
var delete = edit_distance_dfs(s, t, i - 1, j);
28-
var replace = edit_distance_dfs(s, t, i - 1, j - 1);
26+
var insert = editDistanceDfs(s, t, i, j - 1);
27+
var delete = editDistanceDfs(s, t, i - 1, j);
28+
var replace = editDistanceDfs(s, t, i - 1, j - 1);
2929
// 返回最少编辑步数
3030
return @min(@min(insert, delete), replace) + 1;
3131
}
3232

3333
// 编辑距离：记忆化搜索
34-
fn edit_distance_dfs_mem(comptime s: []const u8, comptime t: []const u8, mem: anytype, i: usize, j: usize) i32 {
34+
fn editDistanceDfsMem(comptime s: []const u8, comptime t: []const u8, mem: anytype, i: usize, j: usize) i32 {
3535
// 若 s 和 t 都为空，则返回 0
3636
if (i == 0 and j == 0) {
3737
return 0;
@@ -50,19 +50,19 @@ fn edit_distance_dfs_mem(comptime s: []const u8, comptime t: []const u8, mem: an
5050
}
5151
// 若两字符相等，则直接跳过此两字符
5252
if (s[i - 1] == t[j - 1]) {
53-
return edit_distance_dfs_mem(s, t, mem, i - 1, j - 1);
53+
return editDistanceDfsMem(s, t, mem, i - 1, j - 1);
5454
}
5555
// 最少编辑步数 = 插入、删除、替换这三种操作的最少编辑步数 + 1
56-
var insert = edit_distance_dfs_mem(s, t, mem, i, j - 1);
57-
var delete = edit_distance_dfs_mem(s, t, mem, i - 1, j);
58-
var replace = edit_distance_dfs_mem(s, t, mem, i - 1, j - 1);
56+
var insert = editDistanceDfsMem(s, t, mem, i, j - 1);
57+
var delete = editDistanceDfsMem(s, t, mem, i - 1, j);
58+
var replace = editDistanceDfsMem(s, t, mem, i - 1, j - 1);
5959
// 记录并返回最少编辑步数
6060
mem[i][j] = @min(@min(insert, delete), replace) + 1;
6161
return mem[i][j];
6262
}
6363

6464
// 编辑距离：动态规划
65-
fn edit_distance_dp(comptime s: []const u8, comptime t: []const u8) i32 {
65+
fn editDistanceDp(comptime s: []const u8, comptime t: []const u8) i32 {
6666
comptime var n = s.len;
6767
comptime var m = t.len;
6868
var dp = [_][m + 1]i32{[_]i32{0} ** (m + 1)} ** (n + 1);
@@ -89,7 +89,7 @@ fn edit_distance_dp(comptime s: []const u8, comptime t: []const u8) i32 {
8989
}
9090

9191
// 编辑距离：状态压缩后的动态规划
92-
fn edit_distance_dp_comp(comptime s: []const u8, comptime t: []const u8) i32 {
92+
fn editDistanceDpComp(comptime s: []const u8, comptime t: []const u8) i32 {
9393
comptime var n = s.len;
9494
comptime var m = t.len;
9595
var dp = [_]i32{0} ** (m + 1);
@@ -126,20 +126,20 @@ pub fn main() !void {
126126
comptime var m = t.len;
127127

128128
// 暴力搜索
129-
var res = edit_distance_dfs(s, t, n, m);
129+
var res = editDistanceDfs(s, t, n, m);
130130
std.debug.print("将 {s} 更改为 {s} 最少需要编辑 {} 步\n", .{ s, t, res });
131131

132132
// 记忆搜索
133133
var mem = [_][m + 1]i32{[_]i32{-1} ** (m + 1)} ** (n + 1);
134-
res = edit_distance_dfs_mem(s, t, @constCast(&mem), n, m);
134+
res = editDistanceDfsMem(s, t, @constCast(&mem), n, m);
135135
std.debug.print("将 {s} 更改为 {s} 最少需要编辑 {} 步\n", .{ s, t, res });
136136

137137
// 动态规划
138-
res = edit_distance_dp(s, t);
138+
res = editDistanceDp(s, t);
139139
std.debug.print("将 {s} 更改为 {s} 最少需要编辑 {} 步\n", .{ s, t, res });
140140

141141
// 状态压缩后的动态规划
142-
res = edit_distance_dp_comp(s, t);
142+
res = editDistanceDpComp(s, t);
143143
std.debug.print("将 {s} 更改为 {s} 最少需要编辑 {} 步\n", .{ s, t, res });
144144

145145
_ = try std.io.getStdIn().reader().readByte();

‎chapter_dynamic_programming/knapsack.zig

Lines changed: 14 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -5,24 +5,24 @@
55
const std = @import("std");
66

77
// 0-1 背包：暴力搜索
8-
fn knapsack_dfs(wgt: []i32, val: []i32, i: usize, c: usize) i32 {
8+
fn knapsackDfs(wgt: []i32, val: []i32, i: usize, c: usize) i32 {
99
// 若已选完所有物品或背包无容量，则返回价值 0
1010
if (i == 0 or c == 0) {
1111
return 0;
1212
}
1313
// 若超过背包容量，则只能不放入背包
1414
if (wgt[i - 1] > c) {
15-
return knapsack_dfs(wgt, val, i - 1, c);
15+
return knapsackDfs(wgt, val, i - 1, c);
1616
}
1717
// 计算不放入和放入物品 i 的最大价值
18-
var no = knapsack_dfs(wgt, val, i - 1, c);
19-
var yes = knapsack_dfs(wgt, val, i - 1, c - @as(usize, @intCast(wgt[i - 1]))) + val[i - 1];
18+
var no = knapsackDfs(wgt, val, i - 1, c);
19+
var yes = knapsackDfs(wgt, val, i - 1, c - @as(usize, @intCast(wgt[i - 1]))) + val[i - 1];
2020
// 返回两种方案中价值更大的那一个
2121
return @max(no, yes);
2222
}
2323

2424
// 0-1 背包：记忆化搜索
25-
fn knapsack_dfs_mem(wgt: []i32, val: []i32, mem: anytype, i: usize, c: usize) i32 {
25+
fn knapsackDfsMem(wgt: []i32, val: []i32, mem: anytype, i: usize, c: usize) i32 {
2626
// 若已选完所有物品或背包无容量，则返回价值 0
2727
if (i == 0 or c == 0) {
2828
return 0;
@@ -33,18 +33,18 @@ fn knapsack_dfs_mem(wgt: []i32, val: []i32, mem: anytype, i: usize, c: usize) i3
3333
}
3434
// 若超过背包容量，则只能不放入背包
3535
if (wgt[i - 1] > c) {
36-
return knapsack_dfs_mem(wgt, val, mem, i - 1, c);
36+
return knapsackDfsMem(wgt, val, mem, i - 1, c);
3737
}
3838
// 计算不放入和放入物品 i 的最大价值
39-
var no = knapsack_dfs_mem(wgt, val, mem, i - 1, c);
40-
var yes = knapsack_dfs_mem(wgt, val, mem, i - 1, c - @as(usize, @intCast(wgt[i - 1]))) + val[i - 1];
39+
var no = knapsackDfsMem(wgt, val, mem, i - 1, c);
40+
var yes = knapsackDfsMem(wgt, val, mem, i - 1, c - @as(usize, @intCast(wgt[i - 1]))) + val[i - 1];
4141
// 记录并返回两种方案中价值更大的那一个
4242
mem[i][c] = @max(no, yes);
4343
return mem[i][c];
4444
}
4545

4646
// 0-1 背包：动态规划
47-
fn knapsack_dp(comptime wgt: []i32, val: []i32, comptime cap: usize) i32 {
47+
fn knapsackDp(comptime wgt: []i32, val: []i32, comptime cap: usize) i32 {
4848
comptime var n = wgt.len;
4949
// 初始化 dp 表
5050
var dp = [_][cap + 1]i32{[_]i32{0} ** (cap + 1)} ** (n + 1);
@@ -64,7 +64,7 @@ fn knapsack_dp(comptime wgt: []i32, val: []i32, comptime cap: usize) i32 {
6464
}
6565

6666
// 0-1 背包：状态压缩后的动态规划
67-
fn knapsack_dp_comp(wgt: []i32, val: []i32, comptime cap: usize) i32 {
67+
fn knapsackDpComp(wgt: []i32, val: []i32, comptime cap: usize) i32 {
6868
var n = wgt.len;
6969
// 初始化 dp 表
7070
var dp = [_]i32{0} ** (cap + 1);
@@ -90,20 +90,20 @@ pub fn main() !void {
9090
comptime var n = wgt.len;
9191

9292
// 暴力搜索
93-
var res = knapsack_dfs(&wgt, &val, n, cap);
93+
var res = knapsackDfs(&wgt, &val, n, cap);
9494
std.debug.print("不超过背包容量的最大物品价值为 {}\n", .{res});
9595

9696
// 记忆搜索
9797
var mem = [_][cap + 1]i32{[_]i32{-1} ** (cap + 1)} ** (n + 1);
98-
res = knapsack_dfs_mem(&wgt, &val, @constCast(&mem), n, cap);
98+
res = knapsackDfsMem(&wgt, &val, @constCast(&mem), n, cap);
9999
std.debug.print("不超过背包容量的最大物品价值为 {}\n", .{res});
100100

101101
// 动态规划
102-
res = knapsack_dp(&wgt, &val, cap);
102+
res = knapsackDp(&wgt, &val, cap);
103103
std.debug.print("不超过背包容量的最大物品价值为 {}\n", .{res});
104104

105105
// 状态压缩后的动态规划
106-
res = knapsack_dp_comp(&wgt, &val, cap);
106+
res = knapsackDpComp(&wgt, &val, cap);
107107
std.debug.print("不超过背包容量的最大物品价值为 {}\n", .{res});
108108

109109
_ = try std.io.getStdIn().reader().readByte();

‎chapter_dynamic_programming/min_cost_climbing_stairs_dp.zig

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@
55
const std = @import("std");
66

77
// 爬楼梯最小代价：动态规划
8-
fn min_cost_climbing_stairs_dp(comptime cost: []i32) i32 {
8+
fn minCostClimbingStairsDp(comptime cost: []i32) i32 {
99
comptime var n = cost.len - 1;
1010
if (n == 1 or n == 2) {
1111
return cost[n];
@@ -23,7 +23,7 @@ fn min_cost_climbing_stairs_dp(comptime cost: []i32) i32 {
2323
}
2424

2525
// 爬楼梯最小代价：状态压缩后的动态规划
26-
fn min_cost_climbing_stairs_dp_comp(cost: []i32) i32 {
26+
fn minCostClimbingStairsDpComp(cost: []i32) i32 {
2727
var n = cost.len - 1;
2828
if (n == 1 or n == 2) {
2929
return cost[n];
@@ -44,10 +44,10 @@ pub fn main() !void {
4444
comptime var cost = [_]i32{ 0, 1, 10, 1, 1, 1, 10, 1, 1, 10, 1 };
4545
std.debug.print("输入楼梯的代价列表为 {any}\n", .{cost});
4646

47-
var res = min_cost_climbing_stairs_dp(&cost);
47+
var res = minCostClimbingStairsDp(&cost);
4848
std.debug.print("输入楼梯的代价列表为 {}\n", .{res});
4949

50-
res = min_cost_climbing_stairs_dp_comp(&cost);
50+
res = minCostClimbingStairsDpComp(&cost);
5151
std.debug.print("输入楼梯的代价列表为 {}\n", .{res});
5252

5353
_ = try std.io.getStdIn().reader().readByte();

0 commit comments

Comments
 (0)