刷题_9：另类加法 and 走方格的方案数

谁借莪１个温暖的怀抱￠ 2023-09-29 22:58 76阅读 0赞

### 一.另类加法 ###

**题目链接：**

> [另类加法][Link 1]

**题目描述：**

> **给定两个int A和B。编写一个函数返回A+B的值，但不得使用+或其他算数运算符。**

**示例1：**

> **输入：  
> 1， 2  
> 输出：  
> 3**

**个人总结：**

> **使用位运算（&和^）实现简单的加法。**

**代码实现：**

import java.util.*;
    
    public class UnusualAdd {
        
        public int addAB(int A, int B) {
        
            // write code here
            while (B != 0) {
        
                //储存进位信息
                int add = (A & B) << 1;
                //进行不进位的二进制加法
                A ^= B;
                //将进位值赋值给B继续进行不进位的加法 直到 B == 0
                B = add;
            }
            return A;
        }
    }

--------------------

### 二.走方格的方案数 ###

**题目链接：**

> [走方格的方案数][Link 2]

**题目描述：**

> **请计算n\*m的棋盘格子（n为横向的格子数，m为竖向的格子数）从棋盘左上角出发沿着边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。  
> 注：沿棋盘格之间的边缘线行走  
> 数据范围： 1≤n,m≤8**

**输入描述：**

> **输入两个正整数n和m，用空格隔开。(1≤n,m≤8)**

**输出描述：**

> **输出一行结果**

**示例1：**

> **输入：  
> 2 2  
> 输出：  
> 6**

**个人总结：**

> **我们以一个3 \* 4的格子来看该问题，图片如下，我们可以知道3 \* 4的格子有4 \* 5个落点，很显而易见的可以想到使用动态规划来解这类题，已知只能往右走和往下走，我们定义一个dp数组，其中dp\[i\]\[j\]表示到达下标为\[i，j\]的格子的方案数，那么dp\[i\]\[j\]是不是可以由它的左边(到达\[i - 1, j\]的方案数)和上面(到达\[i,j - 1\]的方案数)递推而来，所以状态转移方程为 `dp[i][j] = dp[i - 1][j] + dp[i][j - 1]`,在该基础上，进行一些边界处理就可以了。**

![在这里插入图片描述][cb1b7b7b1fa14d4bb7c2c3d0051d6431.jpeg]

> **这图画的是真丑呀，绷不住了！**

**代码实现：**

import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[][] dp = new int[n + 1][m + 1];
            for (int i = 0; i <= n; i++) {
        
                for (int j = 0; j <= m; j++) {
        
                    if (i == 0 && j == 0) {
        
                        dp[i][j] = 1;
                    } else if (i == 0) {
        
                        dp[i][j] = dp[i][j - 1];
                    } else if (j == 0) {
        
                        dp[i][j] = dp[i - 1][j];
                    } else {
        
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                    }
                }
            }
            System.out.println(dp[n][m]);
        }
    }

[Link 1]: https://www.nowcoder.com/questionTerminal/e7e0d226f1e84ba7ab8b28efc6e1aebc?f=discussion
[Link 2]: https://www.nowcoder.com/questionTerminal/e2a22f0305eb4f2f9846e7d644dba09b?f=discussion
[cb1b7b7b1fa14d4bb7c2c3d0051d6431.jpeg]: https://img-blog.csdnimg.cn/cb1b7b7b1fa14d4bb7c2c3d0051d6431.jpeg