【算法刷题日记之本手篇】另类加法与走方格的方案数

⭐️前面的话⭐️

本篇文章介绍来自牛客试题广场的两道题题解，分别为【另类加法】和【走方格的方案数】，展示语言java。

博客主页：未见花闻的博客主页
欢迎关注点赞收藏⭐️留言
本文由未见花闻原创，CSDN首发！
首发时间：2022年7月19日
✉️坚持和努力一定能换来诗与远方！
推荐书籍：《算法》，《算法导论》
参考在线编程网站：牛客网力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

• ⭐️另类加法⭐️
• • 题目详情
  • 解题思路
  • 源代码
• 总结
• ⭐️走方格的方案数⭐️
• • 题目详情
  • 解题思路
  • 源代码
• 总结

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

测试样例：

1,2
返回：3

题目链接：不用加减乘除做加法

基本思路： 位运算

解题思路1： 不让我使用加法，我为什么要听你话，我偏要用，反正也能过。

前置知识：

• ^运算符相当于不进位相加。
• &可以判断两操作数位是否都为1，我们可以用来判断是否需要进位。
• <<左移运算符，可以将操作数位左移。

解题思路2：
假设两数为a与b，我们可以使用^来进行不进位的加法a^b，为了知道哪些位需要进位，在执行此步骤之前，先得到tmp = (a&b)<<1的值，这句语句的意思就是得到两数都为1的位，左移1位是为了方便实现进位操作，因为进位不就是在某位的前一位进1吗？

如果tmp==0，表示不需要进位，那么此时我们的加法运算也就结束了，如果tmp!=0，我们需要将tmp与上次无进位加法得到的值再次进行无进位相加，并更新tmp的值，直到tmp为0，才能判定加法已经完成了。

有关^为什么是无进位加法，更详细的内容请参考：剑指 Offer 65. 不用加减乘除做加法

解题思路2代码：

import java.util.*;

public class UnusualAdd {
    public int addAB(int a, int b) {
        // write code here
        while (b != 0) {
            int tmp = (a & b) << 1;
            a ^= b;
            b = tmp;
        }
        return a;
    }
}

不用加减乘除做加法，最容易想到的方法就是位运算，通过了解各种位运算的特点，找出模拟加法的适当方法。
力扣同源题：
371. 两整数之和
面试题 17.01. 不用加号的加法
力扣类似题：
面试题 08.05. 递归乘法
29. 两数相除
50. Pow(x, n)
69. Sqrt(x)
面试题 16.07. 最大数值

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

注：沿棋盘格之间的边缘线行走

数据范围： 1≤n,m≤8

输入描述：

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

输出描述：

输出一行结果

示例1

输入：

2 2

输出：

6

题目链接：走方格的方案数

基本思路： 动态规划

解题思路：
首先我们来分析题目，简单来说题目告诉我们棋盘的行n与列m，我们将行数记为row，列数记为col，然后沿着这个row*col的棋盘中的分割线进行行走，那么其实就是从这个方格边缘线上的一端走到另外一端，对于row*col大小棋盘，在水平方向，他有col个格子，因此就有col+1个端点，同理在竖直方向有row+1个端点。

题目，让我们求从左上角顶点到右下角顶点的路径数，只能向右或向左走。


这道题是典型的路径问题，我们考虑动态规划，我们设左上角为原点，坐标为 ( 0 , 0 ) (0, 0) (0,0)，则终点右下角顶点的坐标为 ( r o w , c o l ) (row,col) (row,col)。

状态定义： 定义 f [ i ] [ j ] f[i][j] f[i][j]表示从原点到 ( i , j ) (i,j) (i,j)位置的路径数。
确定初始状态： 当 i = 0 , j = 0 i = 0,j=0 i=0,j=0时，可以理解从原点到原点，那么路径数为 1 1 1，即 f [ 0 ] [ 0 ] = 1 f[0][0]=1 f[0][0]=1。
状态转移方程： 三种情况：

• i = 0 , j > 0 i=0,j>0 i=0,j>0，点 ( i , j ) (i,j) (i,j)在棋盘上边界，只能经过点 ( i , j − 1 ) (i,j-1) (i,j−1)运动到点 ( i , j ) (i,j) (i,j)，此时 f [ i ] [ j ] = f [ i ] [ j − 1 ] f[i][j]=f[i][j-1] f[i][j]=f[i][j−1]。
• i > 0 , j = 0 i>0,j=0 i>0,j=0，点 ( i , j ) (i,j) (i,j)在棋盘左边界，只能经过点 ( i − 1 , j ) (i-1,j) (i−1,j)运动到点 ( i , j ) (i,j) (i,j)，此时 f [ i ] [ j ] = f [ i − 1 ] [ j ] f[i][j]=f[i-1][j] f[i][j]=f[i−1][j]。
• i > 0 , j > 0 i>0,j>0 i>0,j>0，点 ( i , j ) (i,j) (i,j)不在棋盘左边界与上边界，那么要么经过点 ( i − 1 , j ) (i-1,j) (i−1,j)运动到点 ( i , j ) (i,j) (i,j)，要么经过点 ( i , j − 1 ) (i,j-1) (i,j−1)运动到点 ( i , j ) (i,j) (i,j)，此时路径总数应为 f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i ] [ j − 1 ] f[i][j]=f[i-1][j]+f[i][j-1] f[i][j]=f[i−1][j]+f[i][j−1]

综上分析状态转移方程就出来了：
f [ i ] [ j ] = { f [ i ] [ j ] = 1 , i = 0 , j = 0 f [ i ] [ j ] = f [ i ] [ j − 1 ] , i = 0 , j > 0 f [ i ] [ j ] = f [ i − 1 ] [ j ] , i > 0 , j = 0 f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i ] [ j − 1 ] , i > 0 , j > 0 f[i][j]=left{ begin{array}{c} f[i][j]=1,i=0,j=0\ f[i][j]=f[i][j-1], i=0,j>0\ f[i][j]=f[i-1][j], i>0,j=0\ f[i][j]=f[i-1][j]+f[i][j-1], i>0,j>0 end{array} right. f[i][j]=⎩ ⎨ ⎧​f[i][j]=1,i=0,j=0f[i][j]=f[i][j−1],i=0,j>0f[i][j]=f[i−1][j],i>0,j=0f[i][j]=f[i−1][j]+f[i][j−1],i>0,j>0​

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //沿着边缘线走，那就相当于原网格的顶点作为一个新的格子，顶点数是输入数据(m+1)*(n+1)
        int row = sc.nextInt();
        int col = sc.nextInt();
        
        //路径动态规划
        //状态定义:定义f[i][j]为从(0,0)走到(i,j)位置的路径数
        int[][] f = new int[row+1][col+1];
        //确定初始状态:f[0][0]=1，(0,0)走到(0,0)位置的路径数可以理解为1种
        f[0][0] = 1;
        //状态转移方程:情况1:i=0,j>0,f[i][j]=f[i][j-1](在网格上边缘，路径数为左边那一格的路径数)
        //情况2:i>0,j=0,f[i][j]=f[i-1][j](在网格左边缘，路径数为上边那一格的路径数)
        //情况3:i>0,j>0,f[i][j]=f[i-1][j]+f[i][j-1](不在网格上与左边缘，路径数为左边那一格的路径数加上路径数为上边那一格的路径数)
        for (int i = 0; i <= row; i++) {
            for (int j = 0; j <= col; j++) {
                if (i == 0 && j > 0) {
                    //情况1:
                    f[i][j] = f[i][j-1];
                } else if (i > 0 && j == 0) {
                    //情况2:
                    f[i][j] = f[i-1][j];
                } else if (i > 0 && j > 0) {
                    //情况3:
                    f[i][j] = f[i-1][j] + f[i][j-1];
                }
            }
        }
        System.out.println(f[row][col]);
    }
}

本题为路径问题，常见的解题思路为动态规划，重点是知道如何状态定义，确定初始状态和推导状转移方程。

类似题：
62. 不同路径
63. 不同路径 II

升级题：
64. 最小路径和
120. 三角形最小路径和
931. 下降路径最小和

困难题：
1289. 下降路径最小和 II

推荐参考读物：DP - 路径问题